5.3 Medium Access Contro|—Bus/Tree
`
`187
`
`
`
`TRT = TRTO
`
`TRT = TRT2
`
`(b) Case Ila: (TRT4/2) < n X THT < TRT4
`
`Offered Load
`
`TRT = TRT4
`
`ThroughputofClass1'
`
`ThroughputofClass1‘
`
`Offered Load
`
`TRT = TRTO
`
`TRT = TRT2
`
`TRT =
`2 X PI X THT
`
`TRT = TRT4
`
`(C) Case Ilb: n X THT < (TRT4/2)
`
`FIGURE 5.14 (cont)
`
`uses up all of that time and no class 0 data can be transmitted. Further
`increase in offered load results in renewed increase in the token circu-
`
`lation time. The same pattern repeats for class 2 and class 4 data. There
`is a period when the load increases at a constant token circulation time
`of TRT2, and during that period, class 2 data are gradually crowded out.
`Class 4 data are similarly crowded out at a higher level of load. Finally,
`
`Petitioner Cox Communications — Exhibit 1
`
`EXHIBIT
`
`Ex. 1011
`
`Ex. 101 1
`
`Petitioner Cox Communications - Exhibit 1011 Page 201
`
`

`
`
`
`188 Chapter 5 Local Area Network Architecture
`
`a situation is reached in which only class 6 data are being transmitted,
`and the token circulation time stabilizes at n X THT.
`
`For the second case just mentioned (n X THT < TRT4), we need to
`TRT4 <
`
`examine two subcases. Figure 5.14b shows the case in which
`
`(11 X THT) < TRT4. As before, with increasing load, class 0 and class 2
`traffic are eliminated and the token circulation time increases. At some
`point, the increasing load drives the token circulation time to TRT4. Us-
`ing our simple example, when this point is reached, approximately half
`of the load is class 4 data and the other half is class 6. But, since it x
`THT > TRT4‘, if the load on the network continues to increase, the por-
`tion of the load that is class 6 traffic will also increase. This will cause a
`
`corresponding decrease in class 4 traffic. Eventually, a point is reached
`at which all of the allowable class 6 traffic is being handled during each
`token circulation. This will take an amount of time n X THT and still
`leave some time left over for class 4 data. Thereafter, the total token
`circulation time remains stable at TRT4.
`
`TRT4
`
`As
`Finally, Figure 5.14c shows the case in which 11 X THT <
`before, increasing load eliminates class 0 and class 2 traffic. A point is
`reached at which the token circulation time is 2 X 1'1 X THT, with half
`of the traffic being class 4 and half being class 6. This is a maximum
`throughput-per—tol<en-circulation for class 6. However, the amount of
`class 4 data can continue to increase until the token circulation time is
`TRT4.
`
`Figure 5.15 is a simplified example of a 4—stati0n logical ring with THT
`= 610 and TRT4 : TRT2 = TRTO = 1600. Time is measured in octet
`times. Station 9 always transmits three class 6 frames of 128 octets each.
`Stations 7 and 5 send as many lower-priority frames as possible, of
`lengths 400 and 356 octets, respectively. Station 1 transmits class 6
`frames of 305 octets each. Initially, Station 1 has two frames to transmit
`each time it gets the token, and later has only one frame to send per
`token possession. We assume that the time to pass the token is 19 octet
`times. In the figure, there are two columns of numbers under each sta-
`tion. The value in the left-hand column is the token circulation time
`observed at that station for the previous rotation of the token. The right-
`hand value is the number of frames that station transmits. Each row
`represents one rotation of the token.
`The example begins after a period during which no data frames have
`been sent, so that the token has been rotating as rapidly as possible;
`thus each station measures a token circulation time of 76. In the first
`rotation, Station 9 transmits all of its class 6 frames. When Station 7
`receives the token, it measures a rotation time of 460 since it last received
`
`Petitioner Cox Communications — Exhibit 1011 Page 202
`
`Petitioner Cox Communications - Exhibit 1011 Page 202
`
`

`
`
`
`5.3 Medium Access Contro|—Bus/Tree 189
`
`Medium
`
`
`
`TS=9
`THT=6l0
`
`
`TRTC:XMIT
`TRTC:XMlT
`TRTOXMIT
`TRTC:XMIT
`76 3
`460 3
`1660 U
`1660 2
`2270 3
`2270 0
`1070 2
`[782 2
`1782 3
`1782 0
`1782 0
`1070 2
`1070 3
`1070 2
`1870 U
`l870 2
`1870 3
`1870 U
`1070 2
`1782 2
`1782 3
`1782 0
`1782 0
`1070 2
`1070 3
`1070 2
`1870 0
`1870 2
`l87O 3
`I870 O
`!070 2
`1782 l
`1477 3
`1477'
`1
`1377 1.
`H65 1
`1165 3
`H65 2
`15651
`1921 1
`19213
`19210
`11212
`l4-771
`1477 3
`1477 1
`1877 0
`1165 1
`
`Token
`Rot.
`l
`2
`3
`4
`5
`6
`7
`8
`9
`10
`11
`12
`
`FIGURE 5.15 Operation of a Multiclass Token Bus Protocol
`
`the token (3128 + 4519). Thus it is able to send three of its frames before
`its TRT is exhausted. Station 5 measures a rotation time of 1660 (3’*400
`+ 3*128 + 4*19) and thus is prevented from sending any data. Finally,
`Station 1 sends two class 6 frames.
`
`Note that rotations 5 through 7 repeat rotations 2 through 4, showing
`a stable bandwidth allocation: Stations 1 and 9 use 69% of the band-
`width for class 6 data and Stations 5 and 7 share equally the remaining
`bandwidth for lower—priority data. Starting on the eighth rotation, Sta-
`tion 1 reduces it use of the LAN. This reduces the bandwidth used for
`class 6 data to 52%, and lower-priority data are allowed to fill in the
`unused bandwidth.
`
`CSMA/CD versus Token Bus
`
`At present, CSMA/CD and token bus are the two principal contenders
`for medium access control technique on bus/tree topologies. Table 5.7
`attempts to summarize the pros and cons of the two techniques. A brief
`discussion follows.
`
`Let us look at CSMA/CD first. On the positive side, the algorithm is
`simple; good news for the VLSI folks, and also good news for the user,
`in terms of cost and reliability. The protocol has been widely used for a
`long time, which also leads to favorable cost and reliability. The protocol
`provides fair access—all stations have an equal chance at the bandwidth;
`good if you require only fair access. As we shall see in Chapter 9,
`CSMA/CD exhibits quite good delay and throughput performance, at
`least up to a certain load, around 5 Mbps under some typical conditions.
`
`Petitioner Cox Communications — Exhibit 1011 Page 203
`
`Petitioner Cox Communications - Exhibit 1011 Page 203
`
`

`
`
`
`1 90 Chapter 5 Local Area Network Architecture
`
`TABLE 5.7 CSMA/CD versus Token Bus
`
`Advantages
`
`CSMA/CD
`
`Disadvantages
`
`Simple algorithm
`Widely used
`Fair access
`Good performance at low to medium
`load
`
`Token Bus
`
`Colision detection requirement
`Fault diagnosis problems
`Minimum packet size
`Poor performance under very heavy
`load
`Biased to long transmissions
`
`Excellent throughput performance
`Tolerates large dynamic range
`Regulated access
`
`Complex algorithm
`Unproven technology
`
`There are, unfortunately, quite a few "cons” for CSMAICD. From an
`engineering perspective, the most critical problem is the collision detec-
`tion requirement. In order to detect collisions, the differences in signal
`strength from any pair of stations at any point on the cable must be
`small; this is no easy task to achieve. Other undesirable implications
`flow from the CD requirement. Since collisions are allowed, it is difficult
`for diagnostic equipment to distinguish expected errors from those in-
`duced by noise or faults. Also, CD imposes a minimum frame size,
`which is wasteful of bandwidth in situations where there are a lot of
`short messages, such as may be produced in highly interactive environ-
`ments.
`
`There are some performance problems as well. For certain data rates
`and frame sizes, CSMA/CD performs poorly as load increases. Also, the
`protocol is biased toward long transmissions.
`For token bus, perhaps its greatest positive feature is its excellent
`throughput performance. Throughput increases as the data rate in-
`creases and levels off but does not decline as the medium saturates.
`Further,
`this performance does not degrade as the cable length in-
`creases. A second "pro” for token bus is that, because stations need not
`detect collisions, a rather large dynamic range is possible. All that is
`required is that each station's signal be strong enough to be heard at all
`points on the cable; there are no special requirements related to relative
`signal strength.
`Another strength of token bus is that access to the medium can be
`regulated. If fair access is desired, token bus can provide this as well as
`CSMA/CD. Indeed, at high loads, token bus may be fairer; it avoids the
`last-in,
`first—out phenomenon mentioned earlier.
`If priorities are re-
`quired, as they may be in an operational or real—time environment, these
`can be accommodated. Token bus can also guarantee a certain band-
`
`Petitioner Cox Communications — Exhibit 1011 Page 204
`
`Petitioner Cox Communications - Exhibit 1011 Page 204
`
`

`
`5.3 Medium Access Control—Bus/Tree
`
`191
`
`width; this may be necessary for certain types of data, such as voice,
`digital video, and telemetry.
`An advertised advantage of token bus is that it is deterministic; that
`is, there is a known upper bound to the amount of time any station must
`wait before transmitting. This upper bound is known because each sta-
`tion in the logical ring can hold the token only for a specified time. In
`contrast, with CSMA/CD, the delay time can be expressed only statisti-
`cally. Furthermore, since every attempt to transmit under CSMA/CD
`canin principle produce a collision, there is a possibility that a station
`could be shut out indefinitely. For process control and other real-time
`applications, this nondeterministic behavior is undesirable. Alas, in the
`real world,
`there is always a _finite possibility of transmission error,
`which can cause a lost token. This adds a statistical component to token
`bus.
`.
`
`The main disadvantage of token bus is its complexity. The reader who
`madeit through the description above can have no doubt that this is a
`complex algorithm. A second disadvantage is the overhead involved.
`Under lightly loaded conditions, a station may have to wait through
`many fruitless token passes for a turn.
`Which to choose? That is left as an exercise to the reader, based on
`requirements and the relative costs prevailing at the time. The decision
`is also influenced by the baseband versus broadband debate. Both must
`be considered together when comparing vendors.
`
`Centralized Reservation
`
`The CSMA/CD technique was developed to deal with bursty traffic,
`such as is typically produced in interactive applications (query response,
`data entry, transactions). In this environment, stations are not transmit—
`ting most of the time; hence, a station with data to transmit can gener-
`ally seize the channel quickly and with a minimum of fuss. Token bus,
`on the other hand, incurs the overhead of passing the token from one
`idle station to another.
`
`For applications that have a stream rather then bursty nature (file
`transfer, audio, facsimile), token bus can perform quite well, especially
`if some priority scheme is used. If the collective load is great enough,
`CSMA/CD has difficulty keeping up with this kind of demand.
`A number of schemes have been proposed, based on the use of
`reservations, that appear to offer the strengths of both CSMA/CD and
`token bus. In this section we look at a technique that requires centralized
`Control. This is a likely candidate for a broadband system, with the con-
`trol function performed at the headend. In Chapter 6 we will examine a
`decentralized control technique specifically designed for the high data
`rates of HSLNS.
`
`Petitioner Cox Communications — Exhibit 1011 Page 205
`
`Petitioner Cox Communications - Exhibit 1011 Page 205
`
`

`
`192
`
`Chapter 5 Local Area Network Architecture
`
`The centralized scheme described in this section was developed by
`AMDAX for its broadband LAN [KARP82]. (Other centralized reserva-
`tion schemes for bus systems have been described in [W1LL73] and
`[MARK78].) Fixed-size frames of 512 bits are used, of which 72 are over-
`head bits. Time is organized into cycles, each cycle consisting of a set of
`equal-size time slots, and each time slot is sufficient for transmitting one
`frame. At the conclusion of one cycle, another Cycle begins. The central
`controller at the headend may allocate slot or frame positions, within
`one or more future cycles, to particular stations. Frame positions not
`assigned to any station are referred to as unallocated frames. All stations
`must remain informed as to which frames are allocated to them and
`which are unallocated.
`
`From the point of View of the station, communication is as follows. If
`a station has a small message to send, one that will fit in a single frame,
`it sends it in the next available unallocated frame on the inbound chan-
`
`nel. The frame contains the message, source and destination addresses,
`and control information indicating that this is a data frame. Because the
`frame position used by the station is unallocated, it may also be used by
`another station, causing a collision. Hence the transmitting station must
`listen to the outbound channel for its transmission. If the station does
`not see its frame within a short defined time, it continues to send the
`frame at random times until it gets through.
`To send messages too big to fit into a single frame, a station may
`reserve time on the bus. It does this by sending a reservation request to
`the central controller on the inbound channel. The request uses an un-
`allocated frame and contains an indication that this is a request frame,
`the source address, and the number of frames to be sent. The station
`then listens to the outbound channel a short defined time, expecting to
`get a reservation confirmation frame containing its address and the
`number and order of frames in future cycles it has been allocated (if the
`line is too heavily loaded, it may not get all the bandwidth requested).
`When confirmation is received, the station may transmit its data in the
`frames allocated to it. If confirmation is not received, the station as-
`sumes that its reservation suffered a collision and tries again.
`From the point of view of the central controller, communication is as
`follows. Frames are received one at a time on the inbound channel. Al-
`located frames are repeated on the outbound channel with no further
`processing. Unallocated frames must be examined. If the frame is gar-
`bled or contains an error, it is ignored. If it is a valid data frame, it is
`repeated on the outbound channel. If it is a valid reservation frame, the
`controller fills the reservation within the limits of its available frames in
`future cycles and sends a confirmation.
`It should be clear that this technique exhibits the strengths of both
`CSMA/CD and token bus. Its principal disadvantage is that it requires a
`
`Petitioner Cox Communications — Exhibit 1011 Page 206
`
`Petitioner Cox Communications - Exhibit 1011 Page 206
`
`

`
`5.4 Medium Access Contro|—Ring
`
`1 93
`
`rather complex central controller, with the attendant reliability prob-
`lems.
`
`5.4
`
`MEDIUM ACCESS CONTROL—Ri NC.
`
`Over the years, a number of different algorithms have been proposed
`for controlling access to the ring. The three most common access tech-
`niques are discussed in this section: register insertion, slotted ring, and
`token ring. The first two will be briefly described; the token ring is dis-
`cussed in some detail, as this is now an IEEE 802 standard.
`Table 5.8 compares these three methods on a number of characteris-
`tics:
`
`- Transmit opportunity: When may a repeater insert a packet onto the
`ring?
`- Packet purge responsibility: Who removes a packet from a ring to
`avoid its circulating indefinitely?
`- Number of packets on ring: This depends not only on the bit length of
`the ring relative to the relative packet length, but on the access
`method.
`
`- Principle advantage.
`- Principal disadvantage.
`
`The significance of the table entries will become clear as the discus-
`sion proceeds.
`
`Characteristic
`Transmit opportunity
`
`TABLE 5.8 Ring Access Methods
`Register
`Insertion
`Idle state plus
`empty buffer
`Receiver or
`transmitter
`Multiple
`
`Packet purge
`responsibility
`Number of packets on
`ring
`
`Slotted Ring
`Empty slot
`
`Token Ring
`Token
`
`Transmitter
`
`Transmitter
`
`Multiple
`
`One
`
`Principal advantage
`
`Maximum ring
`utilization
`
`Simplicity
`
`Regulated/fair
`access
`
`Principal disadvantage
`
`Purge mechanism
`
`Bandwidth
`waste
`
`Token
`maintenance
`
`Petitioner Cox Communications — Exhibit 1011 Page 207
`
`Petitioner Cox Communications - Exhibit 1011 Page 207
`
`

`
`
`
`194 Chapter 5 Local Area Network Architecture
`
`Token Ring
`
`Token ring is probably the oldest ring control technique, originally pro-
`posed in 1969 [FARM69] and referred to as the Newhall ring. It has be-
`come the most popular ring access technique in the United States. This
`technique is the one ring access method selected for standardization by
`the IEEE 802 Local Network Standards Committee [IEEE89b].
`
`Description. The token ring technique is based on the use of a small
`frame, called a token, that circulates around the ring when all stations
`are idle. A station wishing to transmit must wait until it detects a token
`passing by. It then seizes the token by changing one bit in the token,
`which transforms it from a token to a start-of-frame sequence for a
`frame. The station then appends and transmits the remainder of the
`fields needed to construct a frame (Figure 5.16).
`There is now no token on the ring, so other stations wishing to trans-
`mit must wait. The frame on the ring will make a round trip and be
`purged by the transmitting station. The transmitting station inserts a
`new token on the ring when both of the following conditions have been
`met:
`
`- The station has completed transmission of its frame.
`- The leading edge of its transmitted frame has returned (after a com-
`plete circulation of the ring) to the station.
`
`If the bit length of the ring is less than the frame length, the first
`condition implies the second. If not, a station could release a free token
`after it has finished transmitting but before it begins to receive its own
`transmission; the second condition is not strictly necessary. However,
`use of the first condition alone might complicate error recovery, since
`several frames may be on the ring at the same time. in any case, the use
`of a token guarantees that only one station at a time may transmit.
`When a transmitting station releases a new free token, the next sta-
`tion downstream with data to send will be able to seize the token and
`transmit.
`
`Several implications of the token ring technique can be mentioned.
`Note that under lightly loaded conditions, there is some inefficiency
`since a station must wait for the token to come around before transmit-
`
`ting. However, under heavy loads, which is where it matters, the ring
`functions in a round-robin fashion, which is both efficient and fair. To
`see this, refer to Figure 5.16. Note that after station A transmits, it re-
`leases a token. The first station with an opportunity to transmit is D. If
`D transmits, it then releases a token and C has the next opportunity,
`and so on. Finally, the ring must be long enough to hold the token. If
`
`Petitioner Cox Communications — Exhibit 1011 Page 208
`
`Petitioner Cox Communications - Exhibit 1011 Page 208
`
`

`
`5.4 Medium Access Contro|—Ring
`
`195
`
`Free Token
`
`
`
`
`Sender Looks for
`Free Token
`
`Changes Free Token
`lo Busy Token and
`Appends Data
`
`Receiver Copies Data
`Addressed To It
`
`Sender Generates
`Free Token Upon
`Receipt Of Physical
`Transmission Header
`(From addressee)
`
`FIGURE 5.16 Token Ring
`
`stations are temporarily bypassed, their delay may need to be supplied
`artificially.
`The principal advantage of token ring is the control over access that
`it provides. In the simple scheme described above, the access is fair. As
`we shall see, schemes can be used to regulate access to provide for prior-
`ity and guaranteed bandwidth services.
`The principal disadvantage of token ring is the requirement for token
`maintenance. Loss of the free token prevents further utilization of the
`ring. Duplication of the token can also disrupt ring operation. One sta-
`
`Petitioner Cox Communications — Exhibit 1011 Page 209
`
`Petitioner Cox Communications - Exhibit 1011 Page 209
`
`

`
`
`
`196 Chapter 5 Local Area Network Architecture
`
`tion must be elected monitor to assure that exactly one token is on the
`ring and to reinsert a free token if necessary.
`
`IEEE 802 Token Ring. The IEEE 802 token ring specification is a re-
`finement of the scheme just outlined. The key elements are as follows:
`
`OJ
`
`1. Single-token protocol: A station that has completed transmission will
`not issue a new token until the busy token returns. This is not as
`efficient for small frames as a multiple-token strategy of issuing a
`free token at the end of a frame. However, the single-token system
`simplifies priority and err0r—recoVery functions.
`2. Priority bits: These indicate the priority of a token and therefore
`which stations are allowed to use the token. In a multiple-priority
`scheme, priorities may be set by station or by message.
`. Monitor bit: Used by the ring monitor, as explained below.
`4. Reservation indicators: They may be used to allow stations with
`high—priority messages to request in a frame that the next token be
`issued at the requested priority.
`5. ToIcen—holding timer: Started at the beginning of data transfer, it con-
`trols the length of time a station may occupy the medium before
`transmitting a token.
`6. Acknowledgment bits: There are three: error detected (E), address
`recognized (A), and frame copied (C). These are set to 0 by the
`transmitting station. Any station may set the E bit. Addressed sta-
`tions may set the A and C bits.
`
`Figure 5.2 shows the two frame formats for token ring. The individual
`fields are as follows:
`
`- Starting delimiter (SD): a unique 8-bit pattern used to start each
`frame.
`
`° Access control (AC): has the format PPPTMRRR, where PPP and RRR
`are 3-bit priority and reservation variables, M is the monitor bit, and
`T indicates whether this is a token or data frame. in the case of a
`
`token frame, the only additional field is ED.
`- Frame control (PC): indicates whether this is an LLC data frame. If
`
`not, bits in this field control operation of the token ring MAC pro-
`tocol.
`- Destination address (DA): as in CSMA/CD and token bus.
`- Source address (SA): as in CSMAJCD and token bus.
`- LLC: as in CSMA/CD and token bus.
`- PCS: as in CSMA/CD and token bus.
`
`- Ending delimiter (ED): contains the error detection (E) bit and the
`intermediate frame (I) bit. The I bit is used to indicate that this is a
`frame other than the final one of a mu1tiple—frame transmission.
`
`Petitioner Cox Communications — Exhibit 1011 Page 210
`
`
`
`Petitioner Cox Communications - Exhibit 1011 Page 210
`
`

`
`5.4 Medium Access Control--Ring
`
`197
`
`- Frame status (PS): contains the address recognized (A) and frame
`copied (C) bits.
`
`Let us first consider the operation of the ring when only a single
`priority is used. In this case, the priority and reservation bits are not
`used. A station wishing to transmit waits until a free token goes by, as
`indicated by a token bit of 0 in the AC field. The station seizes the token
`by setting the token bit to 1. The SD and AC fields of the received token
`now function as the first two fields of a data frame. It then transmits
`
`one or more frames, continuing until either its output is exhausted or
`its tol<en—holding timer expires. When the AC field of the last transrnit-
`ted frame returns, the station transmits a free token by setting the token
`bit to 0 and appending an ED field.
`Stations in the receive mode listen to the ring. Each station can check
`passing frames for errors and set the E bit if an error is detected. If a
`station detects its own address, it sets the A bit to 1; it may also copy
`the frame, setting the C bit to 1. This allows the originating station to
`differentiate three conditions:
`
`- Station nonexistent/nonactive
`
`- Station exists but frame not copied
`- Frame copied
`
`Token Ring Priority. The 802.5 standard includes a specification for an
`optional priority mechanism. Eight levels of priority are supported by
`providing two 3-bit fields in each data frame and token: a priority field
`and a reservation field. To explain the algorithm, let us define the fol-
`lowing variables:
`
`Pf = priority of frame to be transmitted by station
`P5 = service priority: priority of current token
`P, = value of P5 as contained in the last
`token received by this station
`5 = reservation value in current token
`H
`RT
`
`highest reservation in the frames received by
`this station during the last token rotation
`The scheme works as follows:
`
`1. A station wishing to transmit must wait for a token with P5 S. P1,.
`2. While waiting, a station may reserve a future token at its priority
`level (Pf). If a data frame goes by, and if the reservation field is less
`than its priority (R5 < Pf), then the station may set the reservation
`field of the frame to its priority (R5 <— Pf). If a token frame goes by,
`and if (R5 < P, AND P, < P5), then the station sets the reservation
`
`Petitioner Cox Communications — Exhibit 1011 Page 211
`
`Petitioner Cox Communications - Exhibit 1011 Page 211
`
`

`
`
`
`198 Chapter 5 Local Area Network Architecture
`
`field of the frame to its priority (R5 <— Pf). This has the effect of
`preempting any lower-priority reservation.
`3. When a station seizes a token, it sets the token bit to 1 to start a
`data frame, sets the reservation field of the data frame to O, and
`leaves the priority field unchanged (the same as that of the incom-
`ing token frame).
`4. Following transmission of one or more data frames, a station is-
`sues a new token with the priority and reservation fields set as
`indicated in Table 5.9.
`
`The effect of the above steps is to sort the competing claims and allow
`the waiting transmission of highest priority to seize the token as soon
`as possible. A moment's reflection reveals that, as stated, the algorithm
`has a ratchet effect on priority, driving it to the highest used level and
`keeping it there. To avoid this, a station that raises the priority (issues a
`
`(Frame not available OR THT expired)
`AND P, < MAX [R,, Pf]
`AND P, > 5,,
`
`(Frame not available OR THT expired)
`AND P, < MAX [Rh Pfl
`AND P, = SK
`
`TABLE S.9 Actions Performed by the Token Holder to Implement the
`Priority Scheme [VALE92]
`
` Conditions Actions
`Frame available AND PS S Pf
`Send frame
`(Frame not available OR THT expired)
`Send token with:
`AND P, 2 MAX [Rn Pr]
`PS <— Pf
`Rs <— MAX [R,,F‘f]
`Send token with:
`P5 <— MAX [R,, Pf]
`Rs <— 0
`Push S, <— P,
`Push Sx e P5
`Send token with:
`PS <— MAX [RU Pf]
`Rs <~ 0
`Pop Sx
`Push 5x +— PS
`Send token with:
`P5 <— R,
`Rs «— 0
`Pop SK
`Push SX <— P5
`Send token with:
`(Frame not available OR
`P5 9 R,
`(Frame available and Pf < Sx))
`Rs 6- 0
`AND P5 = 5,,
`Pop 3,
`AND R, 5 5,
`Pop Sx
`
`(Frame not available OR
`(Frame available and Pf < S,,))
`AND P5 = 5,,
`AND R, > 5,
`
`Petitioner Cox Communications — Exhibit 1011 Page 212
`
`Petitioner Cox Communications - Exhibit 1011 Page 212
`
`

`
`5.4 Medium Access Contro|—Ring
`
`199
`
`token that has a higher priority than the token that it received) has the
`responsibility of later lowering the priority to its previous level. There-
`fore, a station that raises priority must remember both the old and the
`new priorities and downgrade the priority of the token at the appropri-
`ate time. In essence, each station is responsible for assuring that no
`token circulates indefinitely because its priority is too high. By remem-
`bering the priority of earlier transmissions, a station can detect this con-
`dition and downgrade the priority to a previous,
`lower priority or
`reservation.
`
`To implement the downgrading mechanism, two stacks are main-
`tained by each station, one for reservations and one for priorities:
`
`5;, = stack used to store new values of token priority
`5, 2 stack used to store old values of token priority
`
`The reason that stacks rather than scalar variables are required is that
`the priority can be raised a number of times by one or more stations.
`The successive raises must be unwound in the reverse order.
`To summarize, a station having a higher-priority frame to transmit
`than the current frame can reserve the next token for its priority level
`as the frame passes by. When the next token is issued, it will be at the
`reserved priority level. Stations of lower priority cannot seize the token,
`so it passes to the reserving station or an intermediate station with data
`to send of equal or higher priority than the reserved priority level. The
`station that upgraded the priority level is responsible for downgrading
`it to its former level when all higher-priority stations are finished. When
`that station sees a token at the higher priority, it can assume that there
`is no more higher-priority traffic waiting, and it downgrades the token
`before passing it on. Figure 5.17 is an example of the operation of the
`priority mechanism.
`'
`
`To overcome various error conditions, one sta-
`Token Maintenance.
`tion is designated as the active monitor. The active monitor periodically
`issues an active—monitor-present control frame to assure other stations
`that there is an active monitor on the ring. To detect a lost token con-
`dition, the monitor uses a valid frame timer that is greater than the time
`required to completely traverse the ring. The timer is reset after every
`valid token or data frame. If the timer expires, the monitor issues a to-
`ken. To detect a persistently circulating data frame, the monitor sets a
`monitor bit to 1 on any passing data frame the first time it goes by. If it
`sees a data frame with the monitor bit already set, it knows that the
`transmitting station failed to absorb the frame. The monitor absorbs the
`frame and transmits a token. The same strategy is used to detect a fail-
`ure in the priority mechanism: no token should circulate completely
`around the ring at a constant nonzero priority level. Finally, if the active
`
`Petitioner Cox Communications — Exhibit 1011 Page 213
`
`Petitioner Cox Communications - Exhibit 1011 Page 213
`
`

`
`200
`
`Chapter 5 Local Area Network Architecture
`
`0 A is Sending to B
`
`0 D Makes ai-ligher
`Priority Level
`Reservation
`
`I A Generates a
`Higher Priority
`Level Free
`Token and
`Remembers
`Pi-eempting the
`Lower Priority
`
`0 D Uses the Free
`Token to send
`Data to E
`
`NOTE:
`A, B,C: Low Priority
`D: High Priority
`E: Other Priority
`
`FIGURE 5.17 Token Ring Priority Scheme
`
`monitor detects evidence of another active monitor, it immediately goes
`into standby monitor status.
`In addition, all of the active stations on the ring cooperate to provide
`each station with a continuous update on the identity of its upstream
`neighbor. Each station periodically issues a standby-monitor-present
`(SMP) frame. Its downstream neighbor absorbs this frame, notes its
`ending address, and after a pause, sends its own SMP frame. The ab-
`sence of SMP frames can be used in fault isolation.
`
`Petitioner Cox Communications — Exhibit 1011 Page 214
`
`Petitioner Cox Communications - Exhibit 1011 Page 214
`
`

`
`5.4 Medium Access Contro|—Ring
`
`201
`
`0 D Generates Free
`Taken (at
`Current Priority
`Level)
`
`I A Sees the high
`Priority Free
`Token
`
`And...
`
`0 A Generates a Free
`Token at the
`P1-eempted
`Priority Level
`
`FIGURE 5.17 (Cont)
`
`Register Insertion
`
`This strategy was originally proposed in [HAFN74] and has been devel-
`oped by researchers at Ohio State University [REAM75, LIU78]. It is also
`the technique used in the IBM Series 1 product [IBM82] and a Swiss
`product called SILK [HUBE83]. It derives its name from the shift register
`associated with each node on the ring. The shift register, equal in size
`to the maximum frame length, is used for temporarily holding frames
`
`Petitioner Cox Communications — Exhibit 1011 Page 215
`
`Petitioner Cox Communications - Exhibit 1011 Page 215
`
`

`
`202
`
`Chapter 5 Local Area Network Architecture
`
`that circulate past the node. In addition, the node has a buffer for storing
`locally produced frames.
`The register insertion ring can be explained with reference to Figure
`5.18, which shows the shift register and buffer at one node. First con-
`sider the case in which the station has no data to send, but is merely
`handling frames of data that circulate by its position. When the ring is
`idle, the input pointer points to the rightmost position of the shift reg-
`ister, indicating that it is empty. When data arrive from the ring, they
`are inserted bit by bit in the shift register, with the input pointer shifting
`left for each bit. The frame begins with an address field. As soon as the
`entire address field is in the register, the station can determine if it is
`the addressee. If not, the frame is forwarded by shifting one bit out on
`the right as each new bit arrives from the left, with the input pointer
`stationary. After the last bit of the frame has arrived, the station contin-
`ues to shift hits out to the right until the frame is gone. If, during this
`time, no additional frames arrive, the input pointer will return to its
`initial position. Otherwise, a second frame will begin to accumulate in
`the regist