`
`V21X(cid:1) F*(cid:1) Nn_cafcnt((cid:1) K*(cid:1) R_ch_l((cid:1) [h^(cid:1) ?*E*(cid:1) Ff_cng [h*(cid:1) Ob_(cid:1) ^_mcah(cid:1) i`(cid:1) g chcg og )]imn(cid:1) m_l)(cid:1)
`pcp[\f_(cid:1) h_nqilem*(cid:1) ;8 8 8 (cid:1) FaP]b%(cid:1) 6XaRdXc(cid:1) FWT^ah((cid:1) >O)-2$0%6011)02,((cid:1) Iip_g\_l(cid:1)
`-525*
`
`V22X(cid:1) <*R*(cid:1) O[h_h\[og *(cid:1) 6^\_dcTa(cid:1)@Tcf^aZb%(cid:1) Kl_hnc]_)C[ff((cid:1) Dh]*(cid:1) N_]ih^(cid:1) @^cncih*
`
`V23X(cid:1) =*(cid:1) R b_nn_h(cid:1) [h^(cid:1) N*(cid:1) F[jf[h*(cid:1) <(cid:1) bcab(cid:1) j_l`ilg[h]_(cid:1)nin[ffs(cid:1) il^_l_^(cid:1) g ofnc][mn(cid:1)jli)
`ni]if*(cid:1) No\g cnn_^(cid:1) ni(cid:1) <>H(cid:1) Nca]igg(cid:1) -550((cid:1) A_\lo[ls(cid:1) -55/*
`
`V24X(cid:1) G*(cid:1) Ub [ha((cid:1) N*(cid:1) ?__lcha((cid:1) ?*(cid:1) @mnlch((cid:1) N*(cid:1) Nb_he_l((cid:1) [h^(cid:1) ?*(cid:1) U[jj[f[*(cid:1) MNQK6(cid:1) <(cid:1) h_q(cid:1)
`l_miol]_(cid:1) M_N_lQ[ncih(cid:1) jlini]if*(cid:1) Dhn_lh_n(cid:1) ?l[`n*
`
`-./
`
`(cid:36)(cid:38)(cid:55)(cid:44)(cid:57)(cid:44)(cid:54)(cid:44)(cid:50)(cid:49)(cid:15)(cid:3)(cid:40)(cid:36)(cid:15)(cid:3)(cid:55)(cid:36)(cid:46)(cid:40)(cid:16)(cid:55)(cid:58)(cid:50)(cid:15)(cid:3)(cid:21)(cid:46)(cid:15)(cid:3)(cid:53)(cid:50)(cid:38)(cid:46)(cid:54)(cid:55)(cid:36)(cid:53)(cid:15)(cid:3)(cid:40)(cid:91)(cid:17)(cid:3)(cid:20)(cid:19)(cid:19)(cid:23)(cid:15)(cid:3)(cid:83)(cid:17)(cid:3)(cid:21)(cid:23)(cid:19)(cid:3)(cid:82)(cid:73)(cid:3)(cid:26)(cid:27)(cid:26)
`
`
`
`Attachment 4c: ProQuest index record for Document 4
`
`(cid:36)(cid:38)(cid:55)(cid:44)(cid:57)(cid:44)(cid:54)(cid:44)(cid:50)(cid:49)(cid:15)(cid:3)(cid:40)(cid:36)(cid:15)(cid:3)(cid:55)(cid:36)(cid:46)(cid:40)(cid:16)(cid:55)(cid:58)(cid:50)(cid:15)(cid:3)(cid:21)(cid:46)(cid:15)(cid:3)(cid:53)(cid:50)(cid:38)(cid:46)(cid:54)(cid:55)(cid:36)(cid:53)(cid:15)(cid:3)(cid:40)(cid:91)(cid:17)(cid:3)(cid:20)(cid:19)(cid:19)(cid:23)(cid:15)(cid:3)(cid:83)(cid:17)(cid:3)(cid:21)(cid:23)(cid:20)(cid:3)(cid:82)(cid:73)(cid:3)(cid:26)(cid:27)(cid:26)
`
`
`
`Attachment 4c: ProQuest index record for Document 4
`
`(cid:36)(cid:38)(cid:55)(cid:44)(cid:57)(cid:44)(cid:54)(cid:44)(cid:50)(cid:49)(cid:15)(cid:3)(cid:40)(cid:36)(cid:15)(cid:3)(cid:55)(cid:36)(cid:46)(cid:40)(cid:16)(cid:55)(cid:58)(cid:50)(cid:15)(cid:3)(cid:21)(cid:46)(cid:15)(cid:3)(cid:53)(cid:50)(cid:38)(cid:46)(cid:54)(cid:55)(cid:36)(cid:53)(cid:15)(cid:3)(cid:40)(cid:91)(cid:17)(cid:3)(cid:20)(cid:19)(cid:19)(cid:23)(cid:15)(cid:3)(cid:83)(cid:17)(cid:3)(cid:21)(cid:23)(cid:21)(cid:3)(cid:82)(cid:73)(cid:3)(cid:26)(cid:27)(cid:26)
`
`
`
`Attachment 4d: List of publications citing Document 4 identified by Google Scholar
`
`(cid:36)(cid:38)(cid:55)(cid:44)(cid:57)(cid:44)(cid:54)(cid:44)(cid:50)(cid:49)(cid:15)(cid:3)(cid:40)(cid:36)(cid:15)(cid:3)(cid:55)(cid:36)(cid:46)(cid:40)(cid:16)(cid:55)(cid:58)(cid:50)(cid:15)(cid:3)(cid:21)(cid:46)(cid:15)(cid:3)(cid:53)(cid:50)(cid:38)(cid:46)(cid:54)(cid:55)(cid:36)(cid:53)(cid:15)(cid:3)(cid:40)(cid:91)(cid:17)(cid:3)(cid:20)(cid:19)(cid:19)(cid:23)(cid:15)(cid:3)(cid:83)(cid:17)(cid:3)(cid:21)(cid:23)(cid:22)(cid:3)(cid:82)(cid:73)(cid:3)(cid:26)(cid:27)(cid:26)
`
`
`
`Attachment 4d: List of publications citing Document 4 identified by Google Scholar
`
`(cid:36)(cid:38)(cid:55)(cid:44)(cid:57)(cid:44)(cid:54)(cid:44)(cid:50)(cid:49)(cid:15)(cid:3)(cid:40)(cid:36)(cid:15)(cid:3)(cid:55)(cid:36)(cid:46)(cid:40)(cid:16)(cid:55)(cid:58)(cid:50)(cid:15)(cid:3)(cid:21)(cid:46)(cid:15)(cid:3)(cid:53)(cid:50)(cid:38)(cid:46)(cid:54)(cid:55)(cid:36)(cid:53)(cid:15)(cid:3)(cid:40)(cid:91)(cid:17)(cid:3)(cid:20)(cid:19)(cid:19)(cid:23)(cid:15)(cid:3)(cid:83)(cid:17)(cid:3)(cid:21)(cid:23)(cid:23)(cid:3)(cid:82)(cid:73)(cid:3)(cid:26)(cid:27)(cid:26)
`
`
`
`Attachment 4e: University of Twente Publications index record for a publication
`citing Document 4.
`
`(cid:36)(cid:38)(cid:55)(cid:44)(cid:57)(cid:44)(cid:54)(cid:44)(cid:50)(cid:49)(cid:15)(cid:3)(cid:40)(cid:36)(cid:15)(cid:3)(cid:55)(cid:36)(cid:46)(cid:40)(cid:16)(cid:55)(cid:58)(cid:50)(cid:15)(cid:3)(cid:21)(cid:46)(cid:15)(cid:3)(cid:53)(cid:50)(cid:38)(cid:46)(cid:54)(cid:55)(cid:36)(cid:53)(cid:15)(cid:3)(cid:40)(cid:91)(cid:17)(cid:3)(cid:20)(cid:19)(cid:19)(cid:23)(cid:15)(cid:3)(cid:83)(cid:17)(cid:3)(cid:21)(cid:23)(cid:24)(cid:3)(cid:82)(cid:73)(cid:3)(cid:26)(cid:27)(cid:26)
`
`
`
`Attachment 5a: Copy of Document 5 from the University of Illinois at
`Urbana-Champaign Library
`
`(cid:36)(cid:38)(cid:55)(cid:44)(cid:57)(cid:44)(cid:54)(cid:44)(cid:50)(cid:49)(cid:15)(cid:3)(cid:40)(cid:36)(cid:15)(cid:3)(cid:55)(cid:36)(cid:46)(cid:40)(cid:16)(cid:55)(cid:58)(cid:50)(cid:15)(cid:3)(cid:21)(cid:46)(cid:15)(cid:3)(cid:53)(cid:50)(cid:38)(cid:46)(cid:54)(cid:55)(cid:36)(cid:53)(cid:15)(cid:3)(cid:40)(cid:91)(cid:17)(cid:3)(cid:20)(cid:19)(cid:19)(cid:23)(cid:15)(cid:3)(cid:83)(cid:17)(cid:3)(cid:21)(cid:23)(cid:25)(cid:3)(cid:82)(cid:73)(cid:3)(cid:26)(cid:27)(cid:26)
`
`
`
`Attachment 5a: Copy of Document 5 from the University of Illinois at
`Urbana-Champaign Library
`
`ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1004, p. 247 of 787
`
`
`
`Attachment 5a: Copy of Document 5 from the University of Illinois at
`Urbana-Champaign Library
`
`ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1004, p. 248 of 787
`
`
`
`Attachment 5a: Copy of Document 5 from the University of Illinois at
`Urbana-Champaign Library
`
`ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1004, p. 249 of 787
`
`
`
`Attachment 5a: Copy of Document 5 from the University of Illinois at
`Urbana-Champaign Library
`
`ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1004, p. 250 of 787
`
`
`
`Attachment 5a: Copy of Document 5 from the University of Illinois at
`Urbana-Champaign Library
`
`ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1004, p. 251 of 787
`
`
`
`Attachment 5a: Copy of Document 5 from the University of Illinois at
`Urbana-Champaign Library
`
`ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1004, p. 252 of 787
`
`
`
`Attachment 5a: Copy of Document 5 from the University of Illinois at
`Urbana-Champaign Library
`
`ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR, Ex. 1004, p. 253 of 787
`
`
`
`Attachment 5a: Copy of Document 5 from the University of Illinois at
`Urbana-Champaign Library
`
`(cid:36)(cid:38)(cid:55)(cid:44)(cid:57)(cid:44)(cid:54)(cid:44)(cid:50)(cid:49)(cid:15)(cid:3)(cid:40)(cid:36)(cid:15)(cid:3)(cid:55)(cid:36)(cid:46)(cid:40)(cid:16)(cid:55)(cid:58)(cid:50)(cid:15)(cid:3)(cid:21)(cid:46)(cid:15)(cid:3)(cid:53)(cid:50)(cid:38)(cid:46)(cid:54)(cid:55)(cid:36)(cid:53)(cid:15)(cid:3)(cid:40)(cid:91)(cid:17)(cid:3)(cid:20)(cid:19)(cid:19)(cid:23)(cid:15)(cid:3)(cid:83)(cid:17)(cid:3)(cid:21)(cid:24)(cid:23)(cid:3)(cid:82)(cid:73)(cid:3)(cid:26)(cid:27)(cid:26)
`
`
`
`Attachment 5a: Copy of Document 5 from the University of Illinois at
`Urbana-Champaign Library
`
`(cid:36)(cid:38)(cid:55)(cid:44)(cid:57)(cid:44)(cid:54)(cid:44)(cid:50)(cid:49)(cid:15)(cid:3)(cid:40)(cid:36)(cid:15)(cid:3)(cid:55)(cid:36)(cid:46)(cid:40)(cid:16)(cid:55)(cid:58)(cid:50)(cid:15)(cid:3)(cid:21)(cid:46)(cid:15)(cid:3)(cid:53)(cid:50)(cid:38)(cid:46)(cid:54)(cid:55)(cid:36)(cid:53)(cid:15)(cid:3)(cid:40)(cid:91)(cid:17)(cid:3)(cid:20)(cid:19)(cid:19)(cid:23)(cid:15)(cid:3)(cid:83)(cid:17)(cid:3)(cid:21)(cid:24)(cid:24)(cid:3)(cid:82)(cid:73)(cid:3)(cid:26)(cid:27)(cid:26)
`
`
`
`Attachment 5a: Copy of Document 5 from the University of Illinois at
`Urbana-Champaign Library
`
`(cid:36)(cid:38)(cid:55)(cid:44)(cid:57)(cid:44)(cid:54)(cid:44)(cid:50)(cid:49)(cid:15)(cid:3)(cid:40)(cid:36)(cid:15)(cid:3)(cid:55)(cid:36)(cid:46)(cid:40)(cid:16)(cid:55)(cid:58)(cid:50)(cid:15)(cid:3)(cid:21)(cid:46)(cid:15)(cid:3)(cid:53)(cid:50)(cid:38)(cid:46)(cid:54)(cid:55)(cid:36)(cid:53)(cid:15)(cid:3)(cid:40)(cid:91)(cid:17)(cid:3)(cid:20)(cid:19)(cid:19)(cid:23)(cid:15)(cid:3)(cid:83)(cid:17)(cid:3)(cid:21)(cid:24)(cid:25)(cid:3)(cid:82)(cid:73)(cid:3)(cid:26)(cid:27)(cid:26)
`
`
`
`Attachment 5a: Copy of Document 5 from the University of Illinois at
`Urbana-Champaign Library
`
`(cid:36)(cid:38)(cid:55)(cid:44)(cid:57)(cid:44)(cid:54)(cid:44)(cid:50)(cid:49)(cid:15)(cid:3)(cid:40)(cid:36)(cid:15)(cid:3)(cid:55)(cid:36)(cid:46)(cid:40)(cid:16)(cid:55)(cid:58)(cid:50)(cid:15)(cid:3)(cid:21)(cid:46)(cid:15)(cid:3)(cid:53)(cid:50)(cid:38)(cid:46)(cid:54)(cid:55)(cid:36)(cid:53)(cid:15)(cid:3)(cid:40)(cid:91)(cid:17)(cid:3)(cid:20)(cid:19)(cid:19)(cid:23)(cid:15)(cid:3)(cid:83)(cid:17)(cid:3)(cid:21)(cid:24)(cid:26)(cid:3)(cid:82)(cid:73)(cid:3)(cid:26)(cid:27)(cid:26)
`
`
`
`Attachment 5a: Copy of Document 5 from the University of Illinois at
`Urbana-Champaign Library
`
`(cid:36)(cid:38)(cid:55)(cid:44)(cid:57)(cid:44)(cid:54)(cid:44)(cid:50)(cid:49)(cid:15)(cid:3)(cid:40)(cid:36)(cid:15)(cid:3)(cid:55)(cid:36)(cid:46)(cid:40)(cid:16)(cid:55)(cid:58)(cid:50)(cid:15)(cid:3)(cid:21)(cid:46)(cid:15)(cid:3)(cid:53)(cid:50)(cid:38)(cid:46)(cid:54)(cid:55)(cid:36)(cid:53)(cid:15)(cid:3)(cid:40)(cid:91)(cid:17)(cid:3)(cid:20)(cid:19)(cid:19)(cid:23)(cid:15)(cid:3)(cid:83)(cid:17)(cid:3)(cid:21)(cid:24)(cid:27)(cid:3)(cid:82)(cid:73)(cid:3)(cid:26)(cid:27)(cid:26)
`
`
`
`Attachment 5a: Copy of Document 5 from the University of Illinois at
`Urbana-Champaign Library
`
`(cid:36)(cid:38)(cid:55)(cid:44)(cid:57)(cid:44)(cid:54)(cid:44)(cid:50)(cid:49)(cid:15)(cid:3)(cid:40)(cid:36)(cid:15)(cid:3)(cid:55)(cid:36)(cid:46)(cid:40)(cid:16)(cid:55)(cid:58)(cid:50)(cid:15)(cid:3)(cid:21)(cid:46)(cid:15)(cid:3)(cid:53)(cid:50)(cid:38)(cid:46)(cid:54)(cid:55)(cid:36)(cid:53)(cid:15)(cid:3)(cid:40)(cid:91)(cid:17)(cid:3)(cid:20)(cid:19)(cid:19)(cid:23)(cid:15)(cid:3)(cid:83)(cid:17)(cid:3)(cid:21)(cid:24)(cid:28)(cid:3)(cid:82)(cid:73)(cid:3)(cid:26)(cid:27)(cid:26)
`
`
`
`Attachment 5a: Copy of Document 5 from the University of Illinois at
`Urbana-Champaign Library
`
`(cid:36)(cid:38)(cid:55)(cid:44)(cid:57)(cid:44)(cid:54)(cid:44)(cid:50)(cid:49)(cid:15)(cid:3)(cid:40)(cid:36)(cid:15)(cid:3)(cid:55)(cid:36)(cid:46)(cid:40)(cid:16)(cid:55)(cid:58)(cid:50)(cid:15)(cid:3)(cid:21)(cid:46)(cid:15)(cid:3)(cid:53)(cid:50)(cid:38)(cid:46)(cid:54)(cid:55)(cid:36)(cid:53)(cid:15)(cid:3)(cid:40)(cid:91)(cid:17)(cid:3)(cid:20)(cid:19)(cid:19)(cid:23)(cid:15)(cid:3)(cid:83)(cid:17)(cid:3)(cid:21)(cid:25)(cid:19)(cid:3)(cid:82)(cid:73)(cid:3)(cid:26)(cid:27)(cid:26)
`
`
`
`Attachment 5a: Copy of Document 5 from the University of Illinois at
`Urbana-Champaign Library
`
`(cid:36)(cid:38)(cid:55)(cid:44)(cid:57)(cid:44)(cid:54)(cid:44)(cid:50)(cid:49)(cid:15)(cid:3)(cid:40)(cid:36)(cid:15)(cid:3)(cid:55)(cid:36)(cid:46)(cid:40)(cid:16)(cid:55)(cid:58)(cid:50)(cid:15)(cid:3)(cid:21)(cid:46)(cid:15)(cid:3)(cid:53)(cid:50)(cid:38)(cid:46)(cid:54)(cid:55)(cid:36)(cid:53)(cid:15)(cid:3)(cid:40)(cid:91)(cid:17)(cid:3)(cid:20)(cid:19)(cid:19)(cid:23)(cid:15)(cid:3)(cid:83)(cid:17)(cid:3)(cid:21)(cid:25)(cid:20)(cid:3)(cid:82)(cid:73)(cid:3)(cid:26)(cid:27)(cid:26)
`
`
`
`Attachment 5a: Copy of Document 5 from the University of Illinois at
`Urbana-Champaign Library
`
`(cid:36)(cid:38)(cid:55)(cid:44)(cid:57)(cid:44)(cid:54)(cid:44)(cid:50)(cid:49)(cid:15)(cid:3)(cid:40)(cid:36)(cid:15)(cid:3)(cid:55)(cid:36)(cid:46)(cid:40)(cid:16)(cid:55)(cid:58)(cid:50)(cid:15)(cid:3)(cid:21)(cid:46)(cid:15)(cid:3)(cid:53)(cid:50)(cid:38)(cid:46)(cid:54)(cid:55)(cid:36)(cid:53)(cid:15)(cid:3)(cid:40)(cid:91)(cid:17)(cid:3)(cid:20)(cid:19)(cid:19)(cid:23)(cid:15)(cid:3)(cid:83)(cid:17)(cid:3)(cid:21)(cid:25)(cid:21)(cid:3)(cid:82)(cid:73)(cid:3)(cid:26)(cid:27)(cid:26)
`
`
`
`Attachment 5b: University of Illinois at Urbana-Champaign Library catalog series
`record for IEEE INFOCOM ’92: The Conference on Computer Communications
`
`(cid:36)(cid:38)(cid:55)(cid:44)(cid:57)(cid:44)(cid:54)(cid:44)(cid:50)(cid:49)(cid:15)(cid:3)(cid:40)(cid:36)(cid:15)(cid:3)(cid:55)(cid:36)(cid:46)(cid:40)(cid:16)(cid:55)(cid:58)(cid:50)(cid:15)(cid:3)(cid:21)(cid:46)(cid:15)(cid:3)(cid:53)(cid:50)(cid:38)(cid:46)(cid:54)(cid:55)(cid:36)(cid:53)(cid:15)(cid:3)(cid:40)(cid:91)(cid:17)(cid:3)(cid:20)(cid:19)(cid:19)(cid:23)(cid:15)(cid:3)(cid:83)(cid:17)(cid:3)(cid:21)(cid:25)(cid:22)(cid:3)(cid:82)(cid:73)(cid:3)(cid:26)(cid:27)(cid:26)
`
`
`
`Attachment 5c: Copy of Document 5 from the IEEE Xplore Digital Library
`
`A study on the Inaccessibility Characteristics
`of ISO 8802/4 Token-Bus LANs∗
`
`Jos´e Rufino, Paulo Ver´ıssimo
`Technical University of Lisboa
`INESC†
`e-mail:...ruf@inesc.pt, paulov@inesc.pt
`
`Abstract
`
`Local area networks have long been established as
`the basis for distributed systems. Continuity of service
`and bounded and known message delivery latency are
`requirements of a number of applications, which are
`imperfectly fulfilled by standard LANs. Most previous
`studies have addressed this issue by computing worst-
`case access/transmission delays only for normal LAN
`operation.
`However, LANs are subject to failures, namely par-
`titions. Since most applications can live with tem-
`porary glitches in LAN operation, an alternative ap-
`proach is to quantify all these glitches or temporary
`partitions, that we named inaccessibility, and derive a
`worst-case figure, to be added to the worst-case trans-
`mission delay in absence of faults.
`In these condi-
`tions, reliable real-time operation is possible on non-
`replicated LANs. This paper does an exhaustive study
`of the inaccessibility characteristics of the ISO 8802/4
`token-bus LAN.
`
`1 Introduction
`
`Local area networks have long been established as
`the basis for distributed systems. The several variants
`of standardised LANs (ISO 8802 and FDDI) have dif-
`ferent mechanisms to control access to the medium
`and recover from errors.
`Continuity of service and determinism in transmis-
`sion delay are requirements of a number of applica-
`tions, specially in the fault-tolerance and real-time
`∗
`Paper presented at IEEE INFOCOM’92, the Conference
`on Computer Communications, Florence, Italy, May 6-8 1992,
`CH3133-6/92-0958 c(cid:2)1992 IEEE
`†
`Instituto de Engenharia de Sistemas e Computadores, R.
`Alves Redol, 9 - 6o - 1000 Lisboa - Portugal, Tel.+351-1-
`3155150. This work has been supported in part by the CEC,
`through Esprit Project 1226 - DELTA-4 and by JNICT through
`Programa Ciˆencia.
`
`area, which are unperfectly fulfilled by these LANs, if
`used without special measures. A number of authors
`have studied problems such as priority inversion [1],
`probability of meeting estimated access times [2, 3],
`extensions for medium failure resiliency through re-
`dundancy [4], potential lack of determinism [5].
`In reliable real-time systems, the fundamental re-
`quirement of communications is that there be a
`bounded and known message delivery latency, in the
`presence of disturbing factors such as overload or
`faults. When the requirement is very strict (eg.
`for
`life-critical applications), specialized space-redundant
`architectures are the solution: point-to-point graphs
`[6] or multiple LANs [7]. These solutions are however
`costly and complex.
`In spite of their limitations, standard LANs are a
`very important design component. It is worthwhile in-
`vestigating if the real-time requirement can be reliably
`met in local area networks that are not replicated, ex-
`cept for eventual medium redundancy — at the elec-
`trical signalling level. To achieve reliable real-time
`communication, three fundamental conditions must be
`validated:
`
`1. bounded delay from request to transmis-
`1
`sion of a frame
`, given the worst case load
`conditions assumed;
`2
`
`delivery despite the occurrence of
`2. message
`omission failures (eg. lost frames);
`
`3. control of partitions.
`
`Most of the existing studies with this regard have
`addressed point 1 [2, 8, 9, 10]. However, they are help-
`less at representing the LAN behaviour, when faults
`occur. In that case, it is necessary to study the pat-
`terns for omission failures (eg. number of consecutive
`omission failures) and for partitions.
`
`1LAN level information packet.
`2User level information packet.
`
`1
`
`(cid:36)(cid:38)(cid:55)(cid:44)(cid:57)(cid:44)(cid:54)(cid:44)(cid:50)(cid:49)(cid:15)(cid:3)(cid:40)(cid:36)(cid:15)(cid:3)(cid:55)(cid:36)(cid:46)(cid:40)(cid:16)(cid:55)(cid:58)(cid:50)(cid:15)(cid:3)(cid:21)(cid:46)(cid:15)(cid:3)(cid:53)(cid:50)(cid:38)(cid:46)(cid:54)(cid:55)(cid:36)(cid:53)(cid:15)(cid:3)(cid:40)(cid:91)(cid:17)(cid:3)(cid:20)(cid:19)(cid:19)(cid:23)(cid:15)(cid:3)(cid:83)(cid:17)(cid:3)(cid:21)(cid:25)(cid:23)(cid:3)(cid:82)(cid:73)(cid:3)(cid:26)(cid:27)(cid:26)
`
`
`
`Attachment 5c: Copy of Document 5 from the IEEE Xplore Digital Library
`
`Uncontrolled omissions and partitions are a source
`of asynchrony and inconsistency. This is unaccept-
`able for most systems, let alone real-time ones. Point
`2 is addressed under the scope of the LLC type 3 ser-
`vice for point to point interactions. However, it has
`been practically disregarded for broadcast or multicast
`interactions. One exception is a modified token-ring
`mechanism described in[11]. Point 3, to the authors’
`knowledge, has not been treated for non-replicated
`networks. All three points have been addressed in [12]
`for LANs in general.
`A study of the behaviour of an ISO 8802/4 token-
`bus with regard to partitions is the central issue of this
`paper. Token-bus, given its connection with MAP is
`very relevant in control and automation3, where real-
`time, reliability and accessibility are a must.
`This study contributes to a better understanding
`of the ISO 8802/4 Token-Bus LAN operation having
`these attributes in mind.
`
`2 Controlling Partitions
`
`A network is partitioned when there are subsets
`of the nodes which cannot communicate with each
`other4. In this sense, a single LAN displays a num-
`ber of causes for partition, not all of them of physi-
`cal nature, like bus failure (cable or tap defect): bus
`contention, ring disruption, transmitter or receiver de-
`fects; token loss; etc. Some LANs have means of recov-
`ering from some of these situations, and can/should be
`enhanced to recover from the others, if reliable real-
`time operation is desired.
`However, the recovery process takes time, so in the
`meantime the LAN is partitioned. A solution to the
`problem of controlling partitions was presented in [12].
`It is based on a very simple idea: if one knows for how
`long a network is partitioned, and if those periods are
`acceptably short, real-time operation of the system is
`possible.
`Let us call them periods of inaccessibility, to dif-
`ferentiate from classical partitions. The definition of
`inaccessibility in [13] is summarised here:
`
`Certain kinds of components may temporarily re-
`frain from providing service, without that having
`to be necessarily considered a failure. That state
`is called inaccessibility. It can be made known
`to the users of the component; limits are specified
`(duration, rate); violation of those limits implies
`permanent failure of the component.
`
`3Manufacturing Automation Protocol.
`4The subsets may have a single element. When the network
`is completely down, all partitions have a single element, since
`each node can communicate with no one.
`
`This is not hard to implement, as shown in [12].
`To achieve it one must first assure that all conditions
`leading to partition are recovered from. For exam-
`ple, tolerance to one medium failure is assured in the
`dual FDDI ring [14].
`In a token-bus network some
`extensions have to be implemented, since it has no
`standardised redundancy. For example, we devised a
`glitch-free method for real-time switch-over between
`busses of a dual-media token-bus [4].
`Then, one needs to show that all the inaccessibil-
`ity periods are time-bounded and determine the upper
`bound. The study of ISO 8802/4 token-bus inacces-
`sibility is presented next. The scenarios described in
`the following sections are the inaccessibility periods
`foreseen in the standard specification. The figures pre-
`sented illustrate the intervals in the token-bus opera-
`tion when the LAN does not provide service, although
`not being failed.
`The study yields interesting conclusions, like: a fig-
`ure for the worst case duration of inaccessibility (to
`be added to a worst-case access time...); the existence
`of only one or two periods much longer than average;
`strategies to reduce the longest periods are possible.
`
`3 The Token-Bus Network
`
`The ISO 8802/4 Token-Passing Bus is a local area
`network (LAN) which has gathered a growing atten-
`tion after it has been selected as the communication
`infra-structure of MAP, the Manufacturing Automa-
`tion Protocol, becoming then a standard for intercon-
`nection and interworking in the factory floor [15].
`Access control is performed by a token passing pro-
`tocol, which establishes a logical ring over the physical
`bus. Access to the shared broadcast medium for data
`transmission is only granted to the station which cur-
`rently holds the token. A timed-token mechanism is
`used to guarantee an upper bound on access delay to
`the network. This bound is unfolded with successively
`lower guarantees, in four classes, through priorities.
`The efficiency of this scheme has been studied in
`the last few years, either through simulation work [16]
`or analytical models [2]. The performance of the token
`bus priority scheme [17, 18, 19] has also been studied.
`Analytical approximations for the mean frame delay,
`under different service disciplines, are proposed in [20].
`Most of these studies assume that the network al-
`ways operates normally, neglecting the influence of in-
`accessibility. However, in the presence of faults cor-
`rective actions must be performed and in consequence
`the operation of the logical ring is affected, sometimes
`severely, in the sense that it can no longer ensure the
`calculated frame transmission delay bound.
`
`2
`
`(cid:36)(cid:38)(cid:55)(cid:44)(cid:57)(cid:44)(cid:54)(cid:44)(cid:50)(cid:49)(cid:15)(cid:3)(cid:40)(cid:36)(cid:15)(cid:3)(cid:55)(cid:36)(cid:46)(cid:40)(cid:16)(cid:55)(cid:58)(cid:50)(cid:15)(cid:3)(cid:21)(cid:46)(cid:15)(cid:3)(cid:53)(cid:50)(cid:38)(cid:46)(cid:54)(cid:55)(cid:36)(cid:53)(cid:15)(cid:3)(cid:40)(cid:91)(cid:17)(cid:3)(cid:20)(cid:19)(cid:19)(cid:23)(cid:15)(cid:3)(cid:83)(cid:17)(cid:3)(cid:21)(cid:25)(cid:24)(cid:3)(cid:82)(cid:73)(cid:3)(cid:26)(cid:27)(cid:26)
`
`
`
`Attachment 5c: Copy of Document 5 from the IEEE Xplore Digital Library
`
`An analysis of the Token-Bus error handling mech-
`anisms is provided in [21]. However, it is only qualita-
`tive. This paper makes a quantitative analysis of the
`8802/4 error handling mechanisms in a comprehensive
`way.
`
`Data Rate Bit Time Octect Time
`(M bps)
`tbit (μs)
`toct (μs)
`5
`0.2
`1.6
`10
`0.1
`0.8
`
`Station Delay
`tSD (μs)
`11.3
`20.9
`
`Table 1: Station Delay for a MC68824 Token-Bus
`LAN controller
`
`Network Characterization
`
`For our purposes, two important parameters char-
`acterize the basic operation of any ISO 8802/4 Token-
`Bus network:
`(cid:2) Data Rate - The rate of data signalling, in the bus.
`It gives a meaning to the bit and octect times. A wide
`set of MAC protocol timers are scaled by these timing
`references [22].
`(cid:2) Slot Time - This parameter is set up by station man-
`agement entities. It is an aggregate variable account-
`ing for medium access control (MAC) sub-layer in-
`trinsic performance and network size. The slot time
`is usually expressed in octect times, due to its formal
`definition, provided in [22]. In this work, for simplic-
`ity, we use its value expressed in plain time, as given
`by equation:
`
`ring housekeeping functions, essential for normal ring
`membership management, and for the preservation of
`ring integrity in the presence of faults. These functions
`are supported through the following set of actions:
`
`– Solicit new stations for logical ring entry.
`– Find out the successor of a failed station (who fol-
`lows).
`– Solicit any station to respond at successor querying.
`– Resolve contentions.
`– Establish a new successor.
`– Bid for token generation.
`– Token passing.
`The duration of all MAC protocol frames which
`take part in these actions, exception made to token
`claiming, are presented in Table 2, for an address
`length (ladd) of 48 bits. The values were computed
`based on frame lenght and data rate, assuming that
`fast synchronising modems are used. A three octect
`preamble, required to fulfill the minimum 2 μs pream-
`ble duration at 10 Mbps [22], is considered at both
`data rates.
`
`MAC Frame
`
`Symbol
`
`header/trailer
`solicit successor 1
`solicit successor 2
`set successor
`resolve contention
`token
`who follows
`
`tHrT r
`tSS1
`tSS2
`tSSF
`tRC
`tT K
`tW F
`
`Duration (μs)
`5M bps
`10M bps
`35.2
`17.6
`35.2
`17.6
`35.2
`17.6
`44.8
`22.4
`35.2
`17.6
`35.2
`17.6
`44.8
`22.4
`
`(1)
`
`Table 2: Duration of MAC Token-Bus Protocol Data
`Units (ladd = 48)
`
`tSlot = 2 . (tP D + tSD)
`• tP D is the worst case end-to-end propagation
`delay of the physical layer. This variable ac-
`counts for the network cable propagation de-
`lay, plus the modem delays (at both trans-
`mit and receiver ends) and the regenerative re-
`peater delay, whenever used. For the length-
`dependent cable propagation delay a typical
`value of 5 μs/km is assumed.
`• tSD is the station delay. This variable ac-
`counts for the intrinsic performance of each
`particular MAC VLSI implementation. The
`values presented in Table 1 refer to the Mo-
`torola MC68824 Token Bus Controller [23]. A
`typical scenario is considered: the TBC, in ad-
`dition to token passing, is also performing data
`transmissions mixed with ring management ac-
`tions.
`
`MAC Protocol Data Units
`
`Several types of protocol data frames are exchanged
`between peer MAC entities, in order to provide logical
`
`3
`
`4 Accessibility Constraints
`
`In this section we will cover a set of scenarios lead-
`ing to network inaccessibility. For many of them we
`start with very simple situations that then evolve to
`less restrictive – and thus more realistic – operating
`conditions/fault assumptions. For most of the cases,
`the main analysis is completely general, being partic-
`ularized for best and worst cases, afterwards.
`
`Addition Of New Stations
`
`Each station on the logical ring periodically offers
`other stations the opportunity to become ring mem-
`bers. This operation is performed through a controlled
`contention process called solicit successor procedure
`
`(cid:36)(cid:38)(cid:55)(cid:44)(cid:57)(cid:44)(cid:54)(cid:44)(cid:50)(cid:49)(cid:15)(cid:3)(cid:40)(cid:36)(cid:15)(cid:3)(cid:55)(cid:36)(cid:46)(cid:40)(cid:16)(cid:55)(cid:58)(cid:50)(cid:15)(cid:3)(cid:21)(cid:46)(cid:15)(cid:3)(cid:53)(cid:50)(cid:38)(cid:46)(cid:54)(cid:55)(cid:36)(cid:53)(cid:15)(cid:3)(cid:40)(cid:91)(cid:17)(cid:3)(cid:20)(cid:19)(cid:19)(cid:23)(cid:15)(cid:3)(cid:83)(cid:17)(cid:3)(cid:21)(cid:25)(cid:25)(cid:3)(cid:82)(cid:73)(cid:3)(cid:26)(cid:27)(cid:26)
`
`
`
`Attachment 5c: Copy of Document 5 from the IEEE Xplore Digital Library
`
`which allows non-participant stations to declare their
`wish of being admitted into the logical ring. The value
`of a special counter within the MAC sub-layer controls
`how often a ring member can perform management op-
`erations5. The process is initiated by the then-current
`token holding station and its operation varies slightly
`depending on whether or not this station is the one
`having the lowest address.
`Let us consider in first place the case where the cur-
`rent token holder does not have the lowest address, in
`the network. In such a case, the current token holder
`issues a solicit successor 1 frame with the destination
`address set to its successor, waiting afterwards for pos-
`sible responses during a window of one slot time.
`Any station waiting to become a ring member, com-
`pares the addresses of the received solicit successor
`frame with its own address. Only those stations whose
`individual address falls in the range between the ad-
`dresses of the current token holder and its successor
`will respond to the query6 through the issuing of a
`set successor frame. Three distinct situations may
`then occur:
`◦ No station answers - In this case no set successor
`frame is received and the station simply passes the
`token to its former successor, after a one-slot time
`delay.
`◦ Exactly one station answers - Upon the receipt
`of the set successor frame the station updates its
`next station [22] variable and passes the token to this
`new successor. After receiving the token, the new ring
`member can start using it.
`◦ More than one station answer - Contention arises
`when multiple stations simultaneously answer to the
`solicit successor query and, in consequence, only un-
`recognizable noise may be heard during the response
`period. Contention is detected by the solicit successor
`sender and resolved through an arbitration algorithm
`which we will describe ahead. Once contention is re-
`solved, ring management operations proceed, with the
`actions described in the previous case.
`
`The first inaccessibility situation thus occurs when
`the MAC sub-layer, performs the actions required for
`the addition of a new station. The duration of the
`
`5The inter solicit counter [22] is decremented one unit in
`each token rotation; when it reaches zero, ring management op-
`erations can begin, if there is available bandwidth, i.e. provided
`that the time elapsed since the last token visit is lower than
`the associated target token rotation time [22]. This can inhibit
`a large number of stations from performing ring management
`during a single token rotation.
`6This restriction aims at preserving the descending order or-
`ganization of the logical ring. It also serves to reduce the num-
`ber of possible contenders.
`
`resulting inaccessibility period is given by equation 7:
`
`(2)
`
`tina←join1 = tSD + tSS1 + tSlot + trcp
`The exact duration of the resolve contention pro-
`cess – trcp – depends on whether or not a contention
`between stations occurs and on how quickly this con-
`tention is resolved. Contention is detected by the
`solicit successor sender and its resolution is started
`by issuing a resolve contention frame. This action
`opens four response windows. The contending sta-
`tions start to use the first two bits of their station
`addresses,
`in order to establish which of the four
`response windows they will use to respond, with a
`set successor frame. The resolve responder algorithm
`schedules stations with higher T woBit values to re-
`spond sooner. Any station that hears bus activity,
`before issuing its response, withdraws from the con-
`tention process. If a station hears no activity until the
`moment when it should issue the response, it trans-
`mits the set successor frame. The process ends when
`the token holder, at the end of a contending round,
`detects a valid set successor frame. A contending sta-
`tion detects that it has won the contention when it
`receives the token. The resolve responder algorithm is
`won by the first station heard without errors8, usu-
`ally the contending station with the highest address,
`and the average time spent in its resolution can be
`estimated by the corresponding line in equation (3),
`where we have considered that responses are only re-
`ceived near the end of the fourth slot time during 1/4
`of the rounds9:
`
`⎧⎪⎪⎪⎨
`⎪⎪⎪⎩
`
`trcp =
`
`0
`
`(cid:6)
`
`tSSF
`
`no response
`
`no contention
`
`(3)
`
`(tRC + 4 . tSlot + tSSF
`4
`
`)
`
`contention
`
`nbrounds
`
`An upper bound can be placed on trcp. This bound,
`that we signal with superscript wc, is obtained by con-
`sidering that competing stations, with addresses dif-
`fering only in the last two bits, systematically respond
`in the fourth window to the resolve contention request:
`
`7The value of tSD, accounting the overhead needed by a
`station to enter in ring maintenance, may represent a slightly
`pessimistic upper bound. Its straight utilization however, does
`not significantly influence overall computations. It simply aims
`to avoid the introduction of network parameters not defined in
`[22].
`8This is the way the standard specification is written. How-
`ever, a conformant station may use, instead, any correctly re-
`ceived set successor frame [22].
`9Thus spreading out from the four window period.
`
`4
`
`(cid:36)(cid:38)(cid:55)(cid:44)(cid:57)(cid:44)(cid:54)(cid:44)(cid:50)(cid:49)(cid:15)(cid:3)(cid:40)(cid:36)(cid:15)(cid:3)(cid:55)(cid:36)(cid:46)(cid:40)(cid:16)(cid:55)(cid:58)(cid:50)(cid:15)(cid:3)(cid:21)(cid:46)(cid:15)(cid:3)(cid:53)(cid:50)(cid:38)(cid:46)(cid:54)(cid:55)(cid:36)(cid:53)(cid:15)(cid:3)(cid:40)(cid:91)(cid:17)(cid:3)(cid:20)(cid:19)(cid:19)(cid:23)(cid:15)(cid:3)(cid:83)(cid:17)(cid:3)(cid:21)(cid:25)(cid:26)(cid:3)(cid:82)(cid:73)(cid:3)(cid:26)(cid:27)(cid:26)
`
`
`
`Attachment 5c: Copy of Document 5 from the IEEE Xplore Digital Library
`
`Multiple Joins
`
`When a station joins the logical ring through the
`process described in the previous scenario two impor-
`tant actions, decisive for subsequent management op-
`erations, are performed upon ring entry:
`• The inter solicit counter of the new ring member
`is set to zero.
`• Its token rotation timer for ring maintenance
`is set to a special value,
`furnished by station
`management entities,