Telecommunication
`Networks
`
`Mischo Schwartz
`
`Protocols, Modeling ond Anolysis
`
`APL 1012
`APL 1012
`IPR2015-00373
`IPR2015—00373
`
`

`
`
`
`Telecommunication
`Networks: Protocols,
`Modeling and Analysis
`
`MISCHA SCHWARTZ
`
`Department of Electrical Engineering and
`Center for Telecommunications Research
`
`Columbia University
`
`1% Addison-Wesley Publishing Company
`
`Reading, Massachusetts
`Menlo Park, California - Don Mills, Ontario
`Wokingham, England - Amsterdam
`Sydney - Singapore - Tokyo ' Madrid
`Bogota ' Santiago ' San Juan
`
`

`
`This book is in the Addison-Wesley Series in Electrical and Computer Engineering
`
`Sponsoring Editor - Tom Robbins
`Production Supervisor ' Bette]. Aaronsrm
`Copy Editor I Stephanie Kaylin
`Text Designer - Herb Caswell
`Illustrator - Georg: Nichols
`Technical Art Consultant - josepk Vetere
`Production Coordinator - Ezra C. Holster:
`
`Manufacturing Supervisor " Hugh Crawford
`Cover Designer - Marshall Hen1'ic}rs'
`
`
`
`II
`
`Library of Congras Cataloging-in-Publication Data
`
`Schwartz, Mischa.
`Telecommunication networks.
`
`Bibliography: p.
`Includes index.
`
`1. Data transmission systems. 2. Packet switching
`(Data transmission)
`3. Telecommunication--Switching
`systems.
`I. Title.
`Tl{5l05.S385 1987
`ISBN 0-201-16423-X
`
`85-30659
`
`004.6
`
`_
`
`Reprinted with corrections November. 1988
`
`Copyright © 1987 by Addison-Wesley Publishing Company
`
`All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or
`transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, or
`otherwise, without the prior written permission of the publisher. Printed in the United States of
`America.
`
`14 15 "MA 969594
`
`w____‘___:_____‘.___&-...,--,;-4'
`
`',-.—, , -.,,- --,3.,.,-,,,-.-r-;.;.:::;:':..-.-_.._a=.--:¢s;:au.7'--___. .
`
`ha-IMow-.u.1:xfir.»tuI\£:IrJ\'El§r'.!:'9v.'v'5!'n::'.P7'
`
`

`
`4-3 - High-level Doro Link Control (HDLC)
`
`135
`
`4-3 High-level Doro Link Control
`(HDLC)
`
`'
`
`We now focus more specifically on the HD LC protocol, which as already noted
`has fast become an international standard. This protocol followed, and in many
`respects is based on, the IBM SD LC (synchronous data link control). American
`standards activities, paralleling the ISO work and interacting with it, resulted in
`the American National Standards Institute (ANSI) data-link control procedure
`standard ADCCP (advanced data communication control procedure). HDLC
`and ADCCP are closely related and will not be distinguished specifically in this
`discussion [CARLD]. The CCITT X-25-recommended data-link procedures,
`LAPB (balanced link access procedures), a subset of HDLC, will be described in
`some detail- later. All these protocols and others like them are examples of
`bit-oriented protocols, in which the frame structure used eliminates a specific
`dependence on byte or character formatting [SCI-[W 1977].
`In this section we first describe the basic philosophy and operation of
`HDLC, with reference made to the tutorial paper by Carlson [CARLD]. We
`then outline a throughput performance analysis ofone common mode ofopera-
`tion of I-IDLC, following the work of Bux, Kumrnerle, and Truong [BUX
`1980].. The analysis is similar to that carried out in the last section for the
`idealized go—back-N protocol, but because it focuses on a model of a real proto-
`col, it captures the effect of finite sequence numbering and a specific error-
`control procedure. This enables us to compare the idealized - throughput
`analysis with the analysis for a real protocol.
`'
`The standard frame format for HDLC (ADCCP and SDLC have the same
`format) appears in Fig. 4-9. Note that the number of overhead (control) bits is
`3’ = 48, just the number used earlier for calculations. The eight-bit flag se-
`quence 01 11 11 10 that appears at the beginning and end of a frame is used to
`establish and maintain synchronization. Because the flag appears at the begin-
`ning and end of the frame there is no need to prescribe an information field
`structure. The information field (packet) delivered from the network layer
`above can be any desired number of bits. Extended versions of the frame
`structure of Fig. 4-9 are available as well: The address, control, and block-
`check fields can all be increased to allow additional addressing, improved error
`detection, and increased sequence numbers. Since the flags appearing at the
`
`[CARLD] D. E. Carlson, "Bit-oriented Data Link Control Procedures,” IEEE Trans. on
`Comm, vol. COM-28, no. 4, April 1980, 455-467; reprinted in [GREE].
`[BUX 1980] W. Bux, K. Kummerle, and H. L. Truong, “Balanced HDLC Procedures:
`A Performance Analysis,” IEEE Tram. on Comm., vol. COM-28, no. 11, Nov. 1980,
`1889- I898.
`
`

`
`136
`
`Data Link Layer: Examples and Performance Analysis
`
`
`
`{flag}
`01111110
`
`' Sbits -
`.
`.
`
`3 bits
`
`16 bits
`
`(flag)
`01111110
`
`Figure 4_-9 HDLC standard frame format
`
`_ beginning and end of a frame contain six consecutive ones, that sequence may
`not appear anywhere else: in the frame. Bit stuffing is used‘ to eliminate this
`ssibilit _: a zero is inserted "at the transmitter an time that five ones a
`r
`P9
`Y
`.
`.
`Y
`.
`PPCB
`outside the F fields. The zeros are removed at the receiver. Ifseven ones appear
`-anywhere in the frame (six ones followed by an additional one), the frame is
`declared in error;
`Three types of frames are defined to handle information flow, supervisory
`and control signals,'and responses to all of these:
`3 Ifinforrnation transfer)-format
`
`p
`(supervisory) format
`u U (unnumbered) format
`
`S- and U-frames carry no information field. They are used strictly for supervi-
`soryand control purposes. The eight-bit control field in the frame determines
`which type of frame is being transmitted, and, for the S- and U- frames, which
`specific" control signal is being transmitted. Figure 4-10 breaks the eight-bit
`control field down forthe three types of frame. A zero in the first bit of the
`control field corresponds to an‘!-frame. The bit pairs 10 and 1 I appearing as‘ the
`first two bits indicate S-frame and U-frame, respectively, as shown. The two S
`bits in bit positions 3 and -4 of the S_-frame allow four different S-frames to be
`' transmitted. The‘ live M bits in the U-frame allow 32 different U-frames to be
`transmitted. The three-bit number N(S) in the I_-frame represents the sequence
`number of the I-frame. Mod-‘8, sequence numbering is thus standard with nor-
`_mal HDLC. Each successive I-frame has its sequence number incremented by
`one. When the transmitter reaches its maximum sequence number it is forced to
`stop transmitting until a frame in the reverse direction is received, acknowledg-
`ing an outstanding packet. _The N02) bits in the I- and S-frames are used to
`acknowledge I-frames received. The number N(R) acknowledges. the receipt of
`N(_R)-I and any frames preceding that number not already acknowledged. N(R)
`indicates that the receiver is eicfiecting I-frame number N(R). Thus N(R) = 5 (bit
`
`

`
`4-3 - High-level Data Link Control (HDLC)
`
`187
`
`Bit Numberjr
`
`
`
`Figure 4- 10 Control field for the three types of frames
`
`pattern 101) acknowledges the receipt ofI-frame number four (and any preced-
`ing frames not yet acknowledged) and indicates that I-frame number five is
`expected. The N(S) and ;N(R)‘ fields can be extended to seven bits to allow
`mod-128 sequence numbering. The transmitter buffers all frames not yet acked
`positively. Once acked positively the frame can be purged and its sequence
`number used again ..
`-
`Three modes ofoperation are defined for the HDLC protocol [CARLD]:
`1. Normal response mode (NRM). This mode of operation is used in a central-
`ized controi environment. It is suited for polled multipoint operation, in
`which a single primary station communicates with one or more subservient
`secondary stations, the latter being allowed to initiate transmission only in
`response to the primary command. (Polling is described in more detail in
`Chapter 8.)
`
`2. Asynchronous response mode (ARM). This mode is similar to NRM except
`that the secondary station does not need permission from the primary
`station to initiate transmission.
`
`3. Asynchronous balanced mode (ABM). This mode is for point-to-point link
`transmission only, with both stations serving as equal partners. A class of
`procedures for this mode forms the basis for the link level of the X25
`
`
`
`,,‘._._;‘.yHn m«;y:r-.
`
`i
`
`i i
`
`

`
`138
`
`"Data Link Layer: Examples and Performance Analysis
`
`protocol. It is identified there as LAPB [RYBC], which we describe briefly
`in the following paragraphs. Our discussion focuses exclusively on the
`asynchronous balanced mode of operation of HDLC (or ADCCP).
`In HDLC data transmission and error detection and recovery are handled _
`- through the use of the I-frames and S-frames; we discuss only these here. U-
`frames are used in the connect/disconnect phases of the data link procedure, as
`well as to provide extended sequence numbering if desired [CARLD]. As noted
`earlier, there are four possible S—frames, of which only three are used in ABM.
`These three control frames, with their corresponding pair of 5 bits and the
`functions for which they are prescribed, are tabulated as follows:
`
`' NAME
`
`Ready to receive (RR)
`
`3
`
`0
`
`Not ready to receive (RNR)
`
`1
`
`s
`
`FUNCTION
`
`0 N(R) acks all frames received up to
`and including N(R) — I.
`
`0 This provides a How control for a
`temporarily busy condition. N(R)
`also acks all frames up to and includ-
`ing N(R) - 1.
`
`0.
`
`Reject _(RE_[)
`I
`'
`
`1 N(R) rejects all frames from N(R) on.
`It positively acknowledges all frames
`up to and including N(R) - 1.
`Recall that the I-frame also carries an N(R) field that is used for acknowledg-
`ing frames up to and including N(R) — 1. HDLC thus provides both a “piggy-
`-back” feature, with the ack function embedded in an I-frame transmitted in the
`reverse direction, and a separate acknowledgement, called the RR (ready to
`receive) frame, that can be usedto signal a positive ack in the absence_of an
`I-frame or to expedite the delivery ofan ack ifso desired. The RE] (reject) frame
`provides a negative ack (nak) feature if so desired. Note that the ABM subset of
`HDLC uses the go—back-N feature: The REj—frame rejects all I-frames from
`N(R) on. Hence they must all be retransmitted. (The unbalanced modes of
`HDLC also provide for selective reject if desired. The fourth S-frame, labeled
`SRE] for selective reject, calls for retransmission of a particular I-frame.)
`Corresponding to each of the three modes of operation just noted are
`classes of procedure with defined functions and options. For the ABM mode
`these are called balanced asynchronous class (BAC) procedures. The defined
`functions recognize the use of 1, RR, and RNR (not ready to receive) frames, as
`
`.
`
`[RYBC] Antony Rybczynski, “X25 Interface and End-to-End Virtual Circuit Service
`Characteristics," IEEE Trans on Comm, vol. COM-28, no. 4, April 1980, 500-510;
`reprinted in [CREE].
`
`

`
`
`
`4-3 - High-level Data Link Control (I-IDLC)
`
`139
`
`-
`
`well as certain prescribed U-frames used to set up and disconnect the link. Two
`options are added: the use of RE] (option 2) and the restriction that I-frames be
`commands only (option 8). The composite class of procedures is called the BAC
`2,8 class and corresponds to the X.25 link-level LAPB class of procedures.
`[CARLD], [RYBC].
`The concept of command appears in the use of the address field (Fig. 4- 9)
`and the P/F bit (Fig. 4- 10). In the unbalanced modes of HDLC, with their
`recogn-ition specifically of one primary station and one or more secondary
`stations, the address is always that of the secondary station. In the balanced
`(ABM) mode the address is always that of the responding station. Since an
`I-frame is always a command in option 8, the address must be that ofthe receiving
`station. RR and RNR frames may be either commands or responses. If the
`former, the address is that ofthe receiving station. Ifthe latter, the frames carry
`their owniaddress. RE] frames are always considered responses and carry their
`own addresses. The P/F bit enables the command-response mechanism to be
`carried out. A I set in a command is defined to be a P. The response to a P = 1
`must carry F = 1. In the normal response mode the P/F bit is used for polling.
`In the ABM mode, with the BAC 2,8 class of procedures, an I-frarnesent with
`the P bit set equal to 1 requires an S-frame response (RR, RE], RNR) with F = 1 ,
`since the I-frame cannot be a response. An RR with the P bit set will force an
`S-frame with F = 1 to be sent in reply. This P/F procedure is called a checkpoint-
`ing procedure. One example ofits use is to force an immediate ack. On receipt of
`an I-frame with P = 1, an RR with F = I will be sent by the recipient immedi-
`ately, ahead of any I-frames waiting to be transmitted. (This thus induces a
`nonpreemptive priority.) Details appear in [CARLD].
`What are some reasons for invoking the P/F checkpointing procedure, in
`addition to expediting error detection? The procedure can be used to check
`whether an operational data link is present; it can be used to force an early
`acknowledgement ofa particular I-frame, rather than having it indirectly acked
`later by a higher-numbered N(R); it can be used to force transmission ofan RE]
`(i.e., a nak) in case of an error, rather than relying on a timeout mechanism.
`(This might in certain circumstances speed up error recovery and reduce the
`number of frames that might have to be retransmitted in the event of an error.)
`Finally, the procedure could be used for preparing to take a link down (discon-
`nect). In this case it could be used to clean up outstanding acks or other control
`signals. It is important to note that the P/F checkpointing procedure, like others
`in the HDLC repertoire, is optional. Although various_procedures are defined
`specifically‘, others are left undefined, allowing flexibility in the use of the data
`link control.
`
`To provide a better understanding of the use of the various S-frames in the
`ABM mode of I-IDLC, we first follow the typical flow of frames back and forth
`between two stations A-and B. An example appears in Fig. 4 -1 1, which shows
`
`

`
`140
`
`Data Link Layer: Examples and Performance Analysis
`
`
`
`Figure 4- 11 Example of HDLC (ABM) error-free transmission
`
`only the data transfer mode. (See [CARLD, p. 461] for other examples, in-
`cluding the use of U-frames for setting up the link connection.) Error-free
`transmission is assumed. (The errorcase is treated later, in connection with the
`throughput analysis of I-IDLC.)
`The notation used, adapted from [CARLD], is as follows:
`
`1. I-frames." Address, I, N(S), N(R_), P (optional; 1 if used, 0 otherwise)
`Thus Al 1 OP refers to an I—frame' from station B addressed to station A,
`with N(S) = 1, N(R) = 0 (i.e., B is expecting frame 0 from A), and the 'P/F bit
`set to 1. (A reply with F = 1 is thus expected.)
`
`2. S-frames. Address, id, N(R), P/F
`The address, asjust noted, is that of the receiver if a command; itself, if
`a response. The id is RR, RNR, or RE] for each of the three S-frames used.
`N(R) -again acks ali frames up to and inciuding N(R) — 1.P/F is written as!’
`if the frame is a command and as F if a response to a P. (In either case the
`P/F bit is set to 1.)
`"
`
`Station A initiates transmission to station B in the example of Fig. 4- 11 by
`sending an I—frame numbered 0. Station A requests an immediate ack by setting
`P = 1. Since A has not as yet received any I-frames from B, N(R) is set at 0,
`indicating that I-frame 0 is expected from B. In-the meantime station B inde-
`pendently sends two I-frames in succession, A100 and A110. (Station B is also
`expecting I-frame number 0.) On receiving BIOOP, station B immediately sends
`an ack BRRIF. This acknowledges receipt of I-frame 0 from A and indicates
`that frame 1 is expected. Station B later. receives I-frame B110 from A and then
`acknowledges this frame with its own I-frame A122. B follows this frame with
`
`

`
`4-3 I High-level Doro Link Control (HDLC)
`
`141
`
`A132. Both frames are later acked by station A with an RR-frame BRR4P. This
`frame might be used, for example, if station A were now preparing to discon-
`nect. Station B replies with BRRSF.
`
`4-3-1 Throughput Analysis, Balanced HDLC
`Procedure
`
`Following this introduction to some of the aspects of the HDLC protocol,
`we now proceed to a throughput analysis of the procedure. We follow Bux et al.
`[BUX 1980], but for a simplified case only, noted later. Bux et al. also provide a
`time-delay analysis. The reader is referred to their paper, and other papers
`referenced there, for details ofboth the throughput and the time-delay analyses.
`The basic differences between this analysis and that of the idealized go-
`back-N analysis‘ carried out earlier are that finite sequence numbering is in-
`cluded here and that specific error-control features are modeled as well. This
`analysis serves two purposes: It enables us to compare the idealized infinite
`sequence number throughput result with the finite number case, and it provides
`an exercise in modeling a real rather than an idealized protocol.
`It was noted earlier, in discussing some aspects of the HDLC protocol, that
`certain features are not explicitly defined but are left to the implementor to
`allow flexibility in use. This is true specifically of the error-control mechanism.
`Although the S-frames RE], RR, RN R, and the checkpointing (P/F bit) mecha-
`nism are all available for use in error control, specific roles for their use are left
`to the implementor. For example, although receipt of RE] rejects‘ I-frame N0?)
`and all I-frames following, this nak feature does not necessarily have to be used.
`One could choose to implement only the positive ack (either RR or an I-frame)
`with the timeout feature. However, only an analysis ofa specific implementation
`can-be carried out. For this reason Bux et a]. provide some specific rules for the
`use of error control._ These involve the use of the RE] frame, the timeout
`mechanism, and the use of checkpointing (the P/F bit). Specifically, the follow-
`ing stipulations are made:
`
`1. REJ recovery. This is assumed to be always used where possible to speed up
`system recovery. However, it can be used only once for a given frame. It
`cannot be invoked on repeats of that frame.
`
`2. Timeout recovery. This must always be used, in addition to RE] recovery;
`without this feature an isolated I-frame or the last in a sequence of I-frames
`could not be recovered if garbled. (Why not?) In addition, since an RE]
`frame may be used only once per I-frame, multiple losses of a given frame
`must be handled through a timeout.
`
`3. Checkpoint (P/F) use. At the end of a timeout the transmitter sends RRP;
`
`
`
`

`
`142
`
`Doro Link Layer: Examples and Performance Analysis
`
`With this assumption, a replyfrom the receiver is required after the expira-
`tion of each timeout interval.
`
`Using these three rules, we are in a position to calculate the link throughput.
`Following the procedure adopted in our earlier analyses of the stop-and-wait
`and go-back-N protocols, we consider the case where one station only, station A,
`is transmitting. This station is assumed in addition to bein a saturated state: It
`always has frames to send. As noted earlier, this provides the maximum possible
`throughput. The receiving station B then acks with RR or acknowledges nega-
`tively with RE].
`Let the sequence number modulus be M. The condition ‘on the sequence
`number N(S) is then
`-
`
`0sN(S)sM—1
`
`(4-13)
`
`'
`
`As noted earlier, for normal HDLC M = 8; the extended version has M = 128.
`At mostM -- 1 frames can then be outstanding. (Consider the case in which allM
`frames, 0 through M - 1, are outstanding and hence unacknowledged. Since
`N(R).acks all frames up to and including N(R) - 1 and indicates that N(R) is"
`expected, a difficulty arises immediately.) ‘As -lower-number frames are acked,
`their numbers may be used again. This mod-M sequence-numbering mecha-
`nism with acknowledgement thus establishes a variable window of sequence
`numbers that can be used. An example appears in Fig. 4 - 12 for M = 8. Initially
`_ it is assumed that frames 1 — 5 are outstanding and unacknowledged. A window
`of two frames, 6, 7," remains (recall thatM -- 1 frames at most may be outstand-
`ing). In part (b) of Fig. 4 — 12 an ack bearing N(R) = 3 is assumed to have arrived.
`This acks frames 1 and 2, allowing a window of frames 6, 7, 0, l to be used.
`In carrying out the analysis we again assume that all frames are offixed
`length. I-frames are of length 2, sec, 5, = (3 + !’)/C, with Z the packet (informa-
`tion field) length, 3’ the control bits in the frame, and C the link capacity in bps.
`All S-frames are of length t, = 3’/C, with Z’ = 48 bits for the HDLC protocol.
`The one-way propagation delay is again taken to be :9 sec, with processing time
`included. The round-trip acknowledgement time is then
`
`transmitted at 48-kbps link speed, using M = 8 for the terrestrial case and ii};-..-.7
`
`_ and we again take
`
`z,,,,=2z,+ :,
`
`(4-14)
`
`_
`
`z,,,,,=2z,+2t,>t,d,
`
`(4-15) '
`
`(The acknowledgement time is defined to be the time between transmission ofa
`frame and receipt of an ack.) We take the case tad, S (M - 2)t,. This simplifies
`the analysis considerably and is not unduly limiting. This case covers such
`examples as both terrestrial and satellite transmission with 1000-bit frames
`
`*?£<§?;“?駧’.§;:§?‘3§iTz‘l§:35é§;§‘:i§I§%
`
`

`
`4—3 - High-level Dotolink Control (HD'L'c)
`
`‘I43
`
`M = 128 for the satellite case. For smaller frame lengths (or lower transmission
`speeds) or smaller sequence numbers, such that tad‘ > (M - 2)t;, one must, of
`course, use the -analysis covering that case as presented in [BUX -1980].
`Before proceeding with the analysis we provide a simple example of frame
`transmission in the presence oferrors to show how the three error-control rules
`stipulated by Bux et al. are used (see Fig. 4-— 13). The maximum sequence
`number M is taken to be four for simplicity. At most three I-frames can then be
`' outstanding at any time. Since station A always has Lframes waiting-, they are
`"transmitted-consecutively, one after the other, until either M -- 1 =-" 3 frames
`are outstanding, a timeout has occurred with no ad: or nak, or a go—back-N
`-repeat of frames is required due to an error. The notation used in Fig. 4 — 13 is
`the same as i_n Fig. 4- 1 1 except that addresses are dropped. Addresses need not
`be included since all I-frames emanate from station A by hypothesis. Frames
`0-2 are shown proceeding uneventfnlly from station A to station B, each one
`being individually acknowledged by an appropriately numbered RR—frame.
`I-frame 3 is shown being hit by an ‘error during transmission. The receiver in
`this example ignores the faulty frame. When frame 0 arrives it is out of se- '
`quence, however (station B is expecting frame 3), and REJS is returned to A. In
`
`
`
`{3}
`
`~
`
`F
`
`(bl
`
`Figure 4 - 12 Sequence number and window concept
`21. Prior to ack arrival
`
`b. Ack with N(R) = 3 arrives
`
`

`
`«VII:V<.U..—Q—.:ocomm.—o>muustvuo.
`
`
`
`
`
`
`
`mamaso.
`
`
`»..u=_Em_.E:.\J..\,_..._
`
`
`
`...\«_.._¢,.flax,m_._o=£m22._.
`
`
`
`
`
`
`
`...gem.
`
`
`
`T|\xuu_\Lj.jT.\..u£.||v+_.3.A.q.
`
`
`
`
`
`
`
`
`
`
`
`%%%%.%u:3..5.?o>ouo.—-.5.Eumoo_n_E«x..m.Mnvon.
`
`
`

`
`
`
`4-3 - High-level Data Link Control (HDLC)
`
`145
`
`.
`
`the meantime, station A transmits frame 1 and then stops transmitting. (Why?)
`When it receives RE_]3 it repeats frame 3, and again follows this with frames 0
`and 1 (notshown here to avoid cluttering the figure). In this example frame 3 is
`again hit by an error during transmission. Station B does nothing since it has
`alreadysent REJ3 once. The timeout at A then -runs out. Using the Bux et al.
`rule, RROP is sent from A to B to force an ack. (Why is there a 0 -in this frame as
`well as in all other frames from A to B?) B replies with RRSF and, on receipt at A,
`130, I00,
`.
`.
`. are again sent. (In other versions of HDLC one might simply
`repeat the faulty frame andall frames following on expiration of the timeout.)
`The approach adopted to calculate the throughput" for this model of the
`HDLC protocol is the same as the one used earlier to analyze the stop-and-wait
`and go—back-N protocols. One calculates try, the virtual transmission time of a _
`' typical frame, and then inverts this to find the maximum frame (packet)
`throughput. The essential difference here is that either RE] or timeout recovery
`may have to he evoked on an error occurrence, and one must distinguish be-
`tween the two. Note again that with the implementation rules assumed here,
`either RE] or timeout recovery will take place after an initial frame error, but only
`' timeout recovery can be used during "subsequent errors on retransmissions of
`the same frame.
`_
`"Again letting p be the probability that a frame is received in error, the
`virtual transmission time, or the average time required to-transmit a frame of
`length 3,, may be written as
`
`r. = ‘I + pm.) + 2‘, (1 ~p)p*(n — 1)T2
`9:32
`P21,
`
`.
`
`(4— 15)
`
`Here T, represents" the random time -required to transmit the first repeat, E(T1)
`is its average value, and T, is the average time required for transmission on
`subsequent retransmissions. Since the recovery mechanism (timeout recovery)
`will always be the same onretransmissions beyond the first, because of the rule
`used here, T, will be the same on each retransmission. T, will differ, however,
`depending on which recovery mechanism (RE]_ or timeout) happens to be
`invoked.
`
`Note that Eq. (4-16) is very similar to Eq. (4-5), the equation for virtual
`transmission time in the (idealized) go-back-N protocol. In fact, it is apparent
`that if E(T,) =-‘- T, = if, one gets precisely
`(4— 5).
`As just stated, T, , the time required to transmit the first repeat of a faulty
`frame, depends on the error-recovery procedure invoked. One must thus de-
`termine the condition for each to occur and average accordingly. In addition, in
`both cases T, is found to depend on a parameter L, defined to be the maximum
`
`

`
`14-6
`
`Data Link Layer: Exornpies and Performance Analysis
`
`number of I-frames following the one that is disturbed before recovery is
`started. This will be M — 2 if the sequence space (window) has expired (recall
`that M - 1 frames at most can be outstanding at any one time) or the number of
`frames transmitted during a timeout interval, whichever is less. In the latter case
`a frame undergoing transmission at the transmitter when the timeout interval
`runs out is allowed to complete transmission. (The timeout counter thus invokes
`a nonpreemptive interrupt on I-frames awaiting transmission.) I. may thus be
`written in the form
`
`L = inf {M- 2, L.z:,,,,/z,_u+ 1)
`
`(4-17)
`
`with inf (inferior) meaning the “lesser of” and La_l representing the largest
`integer not exceeding a.
`As an example, consider a satellite link with 2:, = 700 msec, 1000—bit
`frames, and C = 48-kbps transmission rate. Using tau, = 2:, _+ 21}, I_:,,,,,/t,J +
`I = 36. For M = 8, L = 6; for M = 128, L = 36. Clearly “sequence number
`starvation" ‘can occur on a satellite link with a sequence number space ofM = 8.
`
`1. Recovery via REj. Consider now the calculation of T, in the case where error
`recovery is invoked via the RE_-] mechanism. Clearly this will occur ifthe RE]
`mechanism comes into play before the effect ofthe timeout expiration is felt.
`As will be seen from studying some typical examples, the condition for this
`to happen is that not all L I-framesfollowing the one under consideration are
`disturbed. (If all L frames following are disturbed timeout recovery will be
`invoked.)
`'
`The detailed calculations depend in turn on two ranges of values for L.
`
`a. L small (for example, to“, is relatively small)
`An example appears in Fig. 4 - 14(a). An error occurs during trans-
`mission of frame 1. We then calculate the time T, required to complete
`the first retransmission of this frame. In this example frame 2 is also
`shown disturbed during transmission. The timeout for frame I expires
`before any frame from B arrives. Frame 3, in the process of being
`transmitted during the expiration ofthe timeout, is allowed to complete,
`and the S-frame RROP is then transmitted to force an ack from station B.
`
`But B receives frame I30 out of order (it is expecting I10) and immedi-
`ately generates REJI. This causes I10 to be retransmitted by A. The
`S~frame response RRIF to station A’s RROP after expiration of the
`- timeout arrives later and is ignored. The RE] mechanism thus is invoked
`before the timeout mechanism, due to receipt of the undisturbed I30 by
`B. Had I30 been disturbed, RE]! would nothave been sent by B, and the
`timeout mechanism would have taken over (RRIF in reply to RROP
`from A). Hence the condition for RE] to take precedence is that noted
`earlier: Not all L frames following the one under consideration (frame 1
`
`

`
`4-3 - High-level Dora Link Control (HDLC)
`
`147
`
`Error
`
`Error
`
`RFIOP
`
`Time-Iv
`
`'
`
`“*t°'-"—'|
`EH Station A —-—n-
`
`Station 3 --Ir
`
`Error
`
`Error
`
`Station A —'—-
`
`Station B -—I-
`
`(x +1)r,—-I-—[!%+1‘|r,—+—r,
`
`T1
`
`.
`
`(hr
`
`'
`
`Figure 4- 14 Example of RE] recovery
`a. Lt, < (x +1)z,+ tad‘
`b. La, 2 (x + 1):, + an.
`
`
`

`
`146
`
`Data Link Layer: Examples and Performance Analysis
`
`in this example) are disturbed. Note that in this case channel A to B is idle
`on receipt of the RE] frame. (This is due either to expiration of a time-
`out, as in this example, or because the-sequence window is closed. M - 1
`unacknowledged frames are then outstanding in this case.)
`There are in general x .<— L - 1 frames disturbed after the one under
`consideration. In the example of Fig. 4- 14(a), x = 1. As indicated in the
`. figure, in general
`-
`
`T,E1.'(x)=(x+ I)t,+t,d+£,
`
`(4-18)
`
`The probability of this event happening is just p"(I - p) (x disturbed
`-frames and one frame received correctly). This case corresponds to L
`small enough so that
`
`Lt,<(x+ 1)z,+ tad,
`
`(4-19)
`
`h. L large (for example, say that to“, is now larger)
`"Specifically, let
`
`Li, 2 (x + 1):, + 2“,
`
`(4-20)
`
`Referring to Fig. 4- 14(b), it is apparent that RE] recovery is now in-
`voked simply because the timeout on frame 1 is so long as to expire after
`the RE] frame asking for a repeat of the frame has been received from
`station B. In this example the numbers have been chosen to have the
`sequence number space in I-frame units, (M - 2)_t,, longer than _the
`timeout interval. Had we chosen (M - 2) < Lt”/t,.J + 1, we would
`have obtained the ‘same result, with the condition that Lt, = (M - 2):, 2
`(x + 1):, + .1,,,.
`From Fig. 4- 14(b) it is apparent that for this case we have
`
`T, E1:(x) =(x+ 1):,+ [L_.:,,,/:,.J+ 1]:,+z,.
`
`(4-21)
`
`again with probability (1 — p)p‘. Comparing with Eq. (4-18), we note
`that Eqs. (4 — 21) and (4 — 18) are very similar, the only difference being
`that the quantity in brackets in Eq._ (4-21) is replaced by rack in
`(4 — 18). Here a frame is in the process of being transmitted on receipt of
`the RE] and it is allowed to go to completion, lengthening the effective
`time T1, as contrasted with the case of Fig. 4—14(a). There the RE]
`arrived with the channel from A to B empty.
`
`2. Timeout recovery. This recovery mechanism is invoked if all L I-frames fol-
`lowing the one initiating the error-recovery procedure are disturbed. This
`happens with probability
`Then either the timeout runs out or the se-
`quence window is exhausted (M — 1 frames are oustanding), whichever
`comes first. Thus there are again two cases to consider. An example of each
`appears in Fig. 4-15. Since all frames sent from A are disturbed, no RE]
`frame can be sent from B, and timeout alone controls the recovery.
`
`

`
`4-3 - High-level Dora unkconuo: (HDLC)
`
`149
`
`Error
`
`Error
`
`Error
`
`Error
`
`Error
`
`RFIOP
`
` Station A-——---
`
`Station B-—---
`
`(a)
`
`
`
`_- toutfl
`
`Error
`
`Error
`
`Error
`
`Error
`
`Error
`
`RFIOP
`
`
`
`(b)
`
`Figure 4- 15 Timeout recovery
`3..
`tom 5 L‘;
`b. rm > Lt,
`
`
`

`
`150
`
`Data Link Layer: Examples ond Performance Analysis
`
`a.‘
`
`to": E Lt!
`Then L = Liam/t,J + 1 < M — 2 in this case. As is apparent from Fig.
`4 — 15(a),
`
`T, = Li,-+ z, + in,‘ + 3, "=* 't(L)
`
`(4-22)
`
`_
`h. 3“, > Lt,
`Then clearly L = M - 2, the sequence window is exhausted before’ the
`timeout expires, and there is an interval between the two events during .
`which the channel from A to B is idle. This case appears in Fig. 4 — I 50)).
`It is apparent that for this case
`'
`
`T:=t....+t,+t.a+t.rEr(L)
`
`(4-23)
`
`almost the result ofEq. (4 —- 22) except for the slight difference in the first
`term.
`
`Combining the results of the RE] and timeout recovery cases, by weighting
`each with the respective probability of occurrence, we get
`L“-I
`
`Em) = 20 (1 — P)P"T(x) + P"T(='~)
`
`(4 - 24)
`
`_
`The functions 1:(x) and 'r(L) depend on the two cases just considered.
`Finally we must calculate T, ,- the average transmission time for each repeat
`of a frame beyond the first retransmission. (See Eq. (4 — 16).) Clearly T2 must be
`the function ‘:(I.) defined in. either Eq. (4 -— 22) or Eq. (4 — 23), since timeout
`recovery only can be invoked for ret