INFORMATION TO USERS
`
`While the most advanced technology has been used to
`photograph and reproduce this manuscript, the quality of
`the reproduction is heavily dependent upon the quality of
`the material submitted. For example:
`
`0 Manuscript pages may have indistinct print. In such
`cases, the best available copy has been filmed.
`
`O Manuscripts may not always be complete. In such
`cases, a note will indicate that it is not possible to
`obtain missing pages.
`
`0 Copyrighted material may have been removed from
`the manuscript. In such cases, a note Will indicate the
`deletion.
`
`Oversize materials (e.g., maps, drawings, and charts) are
`photographed by sectioning the original, beginning at the
`upper left-hand corner and continuing from left. to right in
`equal sections with small overlaps. Each oversize page is
`also filmed as one exposure and is available, for an
`additional charge, as a standard 35mm slide or as a 17”x 23”
`black and white photographic print.
`
`Most photographs reproduce acceptably on positive
`microfilm or microfiche but lack the clarity on xerographic
`copies made from the microfilm. For an additional charge,
`35mm slides of 6”x 9” black and white photographic prints
`are available for any photographs or illustrations that
`cannot be reproduced satisfactorily by xerography.
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 1
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 1
`
`

`

`Petitioner Cisco Systems - Exhibit 1014 - Page 2
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 2
`
`

`

`Order Number 8717240
`
`Triinet: a demand~adaptive media-access protocol for
`metropolitan area networks
`
`Sirazi, Semir, Ph.D.
`
`ILLINOIS INSTITUTE OF TECHNOLOGY, 1987
`
`Copyright ©1986 by Sirazi, Semir. A11 rights reserved.
`
`U-M-I
`
`300 N. Zeeb Rd.
`Ann Arbor, MI 48106
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 3
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 3
`
`

`

`Petitioner Cisco Systems - Exhibit 1014 - Page 4
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 4
`
`

`

`TRIINET: A DEMAND-ADAPTIVE MEDIA-ACCESS
`
`PROTOCOL FOR METROPOLITAN AREA NETHORKS
`
`BY
`
`SEMIR 513321
`
`Submitted in partial fulfillment of the
`requirements of the degree of
`Doctor of Philosophy in Computer Science
`in the School of Advanced Studies of
`Illinois Institute of Technology
`
`
`
`ORlGiNAL ARCHIVAL COPY
`
`Chicago, Illinois
`May, 1986
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 5
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 5
`
`

`

`6:) Copyright by
`Semir Sirazi
`
`1986
`
`ii
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 6
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 6
`
`

`

`ACKNOWLEDGMENT
`
`It
`
`is a great pleasure for me
`
`to express my
`
`appreciation to Professor Graham Campbell, my graduate
`
`adviser and doctoral committee chairman,
`
`for his guidance,
`
`friendship and continued support during the course of
`
`this
`
`research. Sincere thanks are also extended to Professors
`
`Martha Evens. Thomas Christopher, Howard Hill, and An-Chi
`
`Liu for serving on the dissertation committee.
`
`A great appreciation is owed to my parents and sisters
`
`for their gracious support and help in accomplishing my
`
`goals.
`
`S.S.
`
`iii
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 7
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 7
`
`

`

`TABLE OF CONTENTS
`
`ACKNOWLEDGMENT O
`
`O
`
`O
`
`I
`
`O
`
`I
`
`I
`
`O
`
`O
`
`O
`
`C
`
`O
`
`O
`
`O
`
`D
`
`O
`
`I
`
`O
`
`O
`
`C
`
`Page
`iii
`
`LISTOFTABLES....................vii
`
`LISTOFFIGURES V111
`
`LIST or ABBREVIATIONS AND SYMBOLS
`
`ABSTRACT o
`
`c
`
`o
`
`o
`
`o
`
`o
`
`I
`
`o
`
`o
`
`O
`
`o
`
`o
`
`o
`
`.
`
`o
`
`.
`
`o
`
`.
`
`.
`
`o
`
`.
`
`.
`
`o
`
`.
`
`.
`
`o
`
`.
`
`.
`
`c
`
`.
`
`.
`
`a
`
`.
`
`.
`
`o
`
`.
`
`.
`
`o
`
`.
`
`.
`
`xi
`
`o xiii
`
`.
`
`1
`
`CHAPTER
`I.
`
`INTRODUCTION
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`1.1 Evolution of Media-Access
`.
`.
`.
`Protocols
`.
`.
`.
`.
`.
`.
`1.2 Emergence of Metropolitan Area
`Networks .
`.
`.
`.
`.
`.
`.
`.
`.
`.
`Summary of Results .
`.
`.
`.
`.
`.
`
`1.3
`
`.
`
`.
`.
`
`.
`
`.
`.
`
`.
`
`.
`.
`
`II. METROPOLITAN AREA NETWORK CHARACTERISTICS .
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`2.1 Metropolitan Area Network
`Properties
`.
`.
`.
`.
`.
`2.2 Metropolitan Area Network
`.
`.
`.
`.
`Topologies
`.
`.
`.
`.
`.
`2.2.1
`Tree—and-Branch Topology
`2.2.2 Segment-Switched Tree-and-
`Branch Topology
`.2 3 Bus Topology
`2. u Local-Switch Star-Topology
`2. 2.5 Ring Topology
`2.3 Service Characteristics and
`Requirements
`.
`.
`.
`.
`.
`
`.
`
`.
`
`.
`
`.
`
`III.
`
`FUNCTIONAL REQUIREMENTS OF A MEDIA-ACCESS
`PROTOCOL INTENDED FOR METROPOLITAN
`AREA NETWORKS .
`.
`.
`.
`.
`.
`.
`.
`.
`.
`
`.
`
`.
`
`.
`
`.
`
`3.1 Data, Digitized Voice and Video
`.
`Services .
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`3.2 Large Population of Users
`3.3 Applicability to Metropolitan Area
`Network Topologies .
`.
`.
`.
`.
`.
`.
`3.u Layered Architecture and
`.
`.
`.
`Internetworking
`.
`.
`.
`.
`3.5 Robust and Reliable Operation
`.
`.
`3.6
`Low Bit Error Rate .
`.
`.
`.
`.
`.
`.
`3.7 Stable Operation .
`.
`.
`.
`.
`.
`.
`.
`3.8 High Throughput
`.
`.
`.
`.
`.
`.
`.
`.
`3.9
`Permanent Circuit Switching
`3.10 Virtual Circuits and Datagrams .
`
`.
`
`.
`.
`.
`.
`.
`.
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`.
`
`.
`
`.
`.
`.
`.
`.
`.
`.
`
`.
`
`.
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`.
`
`.
`
`.
`.
`.
`.
`.
`.
`.
`
`1
`
`10
`12
`
`20
`
`20
`
`29
`
`43
`
`54
`
`54
`55
`
`57
`
`58
`61
`63
`6H
`65
`67
`6
`
`iv
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 8
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 8
`
`

`

`CHAPTER
`III.
`
`(Continued)
`
`3.11 Multiple Channel Allocation
`3.12 Capacity Assignment on Demand
`3.13 Guaranteed Access With Fairness
`3.1” Adaptivity to Load Fluctuations
`3.15 Priority Handling
`.
`.
`.
`.
`.
`3.16 Low and Predictable Delay
`.
`.
`3.17 Low Cost VLSI Implementation .
`
`.
`
`.
`.
`
`.
`.
`.
`
`.
`.
`.
`.
`.
`.
`.
`
`.
`.
`.
`.
`.
`.
`.
`
`IV.
`
`ANALYSIS OF MEDIA-ACCESS PROTOCOLS FOR
`SATELLITE, RADIO AND LOCAL AREA NETWORKS AS
`APPLIED TO METROPOLITAN AREA NETWORKS .
`.
`.
`
`u.1 Channel Sharing Characteristics
`4.2 Polling-Based Media-Access
`Protocols
`I
`l
`O
`O
`O
`O
`I
`
`O
`
`C
`
`I
`
`”.3
`
`Token Passing-Based Media-Access
`Protocols
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`u.u Contention-Based Media-Access
`
`.
`
`I
`
`.
`
`.
`
`O
`
`.
`
`.
`.
`.
`.
`.
`.
`.
`
`.
`
`.
`
`I
`
`.
`
`.
`.
`.
`.
`.
`.
`.
`.
`.
`Protocols
`u.s Reservation-Based Media-Access
`Protocols
`. .. .
`.
`.
`. .. . o. .
`Summary of Comparative Protocol
`Analysis .
`.
`.
`.
`.
`.
`.
`.
`.
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`4.6
`
`V.
`
`NEW DEMAND—ADAPTIVE MEDIA-ACCESS PROTOCOL
`CHARACTERISTICS .
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`
`5.1
`5.2
`
`.
`.
`.
`.
`.
`.
`.
`.
`General Overview .
`Communication Network Topology and
`Protocol Architecture
`.
`.
`.
`.
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`5.2.1 Hierarchical Network Topology
`5.2.2 Comparison of 031 Reference
`Model vs. Proposed Protocol
`Architecture
`
`Page
`
`71
`73
`7n
`76
`77
`80
`81
`
`82
`
`86
`
`88
`
`106
`
`123
`
`1M9
`
`168
`
`175
`
`175
`
`180
`
`203
`
`213
`
`Frame Check Sequence Field
`Structure .
`.
`.
`.
`.
`.
`Start Delimiter Field
`Control Field
`Source and Destination Address
`Fields
`Data Field
`
`.
`
`.
`
`Subframe Check Sequence Field
`Guard Band
`
`V
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 9
`
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`Frame Structure
`Preamble and Guard Band Fields
`Start Delimiter Field
`Control Field
`Frame Number Field
`
`5.3
`
`O .3:
`
`U'l
`
`
`
`m CU'IU‘U1U1U‘IU'IO'U'IU'IU'IU'IU'I
`
`mac’s.
`
`Pg.0ooJ=J=J=1WWWLNW
`
`34:3:
`
`
`
`GU14:WN-lamzLflN-P (D
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 9
`
`

`

`CHAPTER
`V.
`
`(Continued)
`
`.
`
`.
`
`.
`
`.
`
`.
`
`Page
`
`220
`
`227
`
`23”
`
`238
`
`2A1
`245
`
`265
`
`282
`286
`
`297
`
`302
`
`309
`
`316
`
`.
`
`.
`
`.
`
`.
`.
`
`.
`
`.
`.
`
`.
`
`.
`
`.
`.
`.
`5.5 Packet Formats .
`5.5.1
`Installation Packet
`5.5.2 Network/Station Status Packet
`5.5.3 Acknowledgment Packet
`5.5.” Reservation Packet
`5.5.5 Datagram Packet
`5.5. 6 Statically-Reserved Packet
`5 5.7 DynamicallyuReserved Packet
`5.6 Propagation Delay Compensation .
`.
`.
`5.7
`Frame Synchronization and Subframe
`Slotting .
`.
`.
`.
`.
`.
`.
`.
`.
`.
`5.8 Addressing and Channel
`Segmentation .
`.
`.
`5.9 Priority Assignment and
`.
`.
`.
`.
`Differentiation
`.
`.
`5.10 Static Channel-Time Reservation
`5.10.1
`Frame Reservation
`5.10.2 Subframe Reservation
`5.11 Dynamic Channel-Time Reservation .
`5.11.1
`Frame Reservation
`5.11.2 Subframe Reservation
`5.12 Datagram Transmission Without
`.
`.
`.
`Reservation
`.
`.
`.
`.
`.
`.
`.
`.
`.13 Retransmission Backoff Algorithms
`5.13.1 Priority-Oriented Collision
`Arbitration Algorithm
`5.13.2 Randomly Distributed Retry
`Algorithm
`5.14 Multi-Mode Protocol State Diagram .
`5.15 Estimated Effective Channel
`Utilization
`.
`.
`.
`.
`.
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`.
`
`.
`
`.
`
`.
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`VI.
`
`CONCLUSIONS AND SUGGESTIONS FOR
`FUTURE RESEARCH o
`o
`o
`o
`o
`o
`o
`o
`
`o
`
`o
`
`o
`
`a
`
`o
`
`BIBLIOGRAPHY o
`
`o
`
`o
`
`o
`
`o
`
`o
`
`o
`
`I
`
`o
`
`I
`
`t
`
`o
`
`O
`
`I
`
`o
`
`o
`
`o
`
`o
`
`o
`
`I
`
`I
`
`o
`
`o
`
`vi
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 10
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 10
`
`

`

`LIST OF TABLES
`
`Table
`
`2.1. Comparison of Transmission Media for
`Metropolitan Area Networks
`.
`.
`.
`
`.
`
`.
`
`.
`
`2.2.
`
`Frequency Spectrum Allocation of Coaxial-
`Based Broadband Networks
`.
`.
`.
`.
`.
`.
`.
`
`2.3. Workload Generated from each Source Type
`
`2.”. Data, Voice, and Video Service
`Characteristics .
`.
`.
`.
`.
`.
`
`.
`
`.
`
`.
`
`2.5.
`
`Service Matrix for Metropolitan Area
`Networks
`0
`I
`O
`O
`I
`I
`9
`I
`O
`O
`O
`O
`
`4.1. Comparison of Channel Allocation
`Techniques
`0
`D
`l
`O
`O
`I
`I
`I
`O
`
`O
`
`O
`
`.
`
`O
`
`O
`
`.
`
`O
`
`O
`
`u.2. Traffic Model vs. Media-Access Protocol
`
`5.1. State Diagram of a Frame Control Field
`
`5.2.
`
`Subframe Packet Types .
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`5.3.
`
`Summary of Service Priority Levels
`
`.
`
`.
`
`.
`
`.
`
`.
`
`C
`
`I
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`I
`
`I
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`D
`
`I
`
`.
`
`.
`
`.
`
`.
`
`Page
`
`28
`
`32
`
`45
`
`49
`
`52
`
`89
`
`172
`
`211
`
`217
`
`2H2
`
`vii
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 11
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 11
`
`

`

`LIST OF FIGURES
`
`Tree-and-Branch Topology .
`
`.
`
`.
`
`.
`
`Segment—Switched Tree-and-Branch
`Topology .
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`
`Bus Topology .
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`Local-Switch Star Topology .
`
`Ring Topology
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`Internetworking of Similar Networks
`
`Page
`
`32
`
`35
`
`37
`
`40
`
`42
`
`60
`
`6O
`
`.
`
`.
`
`3
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`Internetworking of Dissimilar Networks .
`
`Polling Protocols: Delay vs. Load vs.
`Throughput
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`
`.
`
`AP, RR, R0: Effect of Propagation Delay
`on Channel Capacity
`.
`.
`.
`.
`.
`.
`.
`.
`
`.
`
`.
`
`AP, RR, R0: Effect of Number of Stations
`on Channel Capacity
`.
`.
`.
`.
`.
`.
`.
`.
`.
`
`Access Delay vs. Throughput vs. Number of
`Active Stations
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`
`Throughput vs. Number of Stations
`in the Ring
`I
`C
`I
`I
`I
`O
`O
`O
`I
`
`0
`
`U
`
`C
`
`Contention-Based Protocols: Throughput
`V3. Traffic
`0
`D
`i
`I
`I
`0
`I
`C
`0
`O
`I
`D
`
`0
`
`I
`
`.
`
`.
`
`.
`
`.
`
`O
`
`O
`
`“.3.
`
`4.“.
`
`“.5.
`
`u.6.
`
`9”
`
`I10
`
`113
`
`11"
`
`116
`
`128
`
`4.7.
`
`Contention-Based Protocols: Effect of
`
`Propagation Delay on Maximum
`Channel Capacity .
`.
`.
`.
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`13a
`
`CSMA-Based Protocols: Channel Capacity vs.
`Queued Stations vs. Packet Length
`.
`.
`.
`
`”.8.
`
`4.9.
`
`Contention Protocols: Throughput vs.
`Normalized Delay .
`.
`.
`.
`.
`.
`.
`.
`.
`
`.
`
`”.10.
`
`Reservation-Based Protocols: Number of
`
`Stations vs. Delay .
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`139
`
`144
`
`155
`
`.
`
`.
`
`.
`
`.
`
`viii
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 12
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 12
`
`

`

`Figure
`
`4.11. STDMA and ATDMA Protocols: Average Delay
`vs. Number of Stations ,
`.
`.
`.
`.
`.
`.
`.
`
`2.12. Reservation-Based Protocols: Throughput
`vs. Average Access Delay .
`.
`.
`.
`.
`.
`
`.
`
`5.1.
`
`Segment Structure in Coaxial-Based HANS
`
`5.2.
`
`MAN Segment Headend
`
`.
`
`.
`
`.
`
`.
`
`5.3. Network Bridge Architecture
`
`.
`
`.
`
`.
`
`.
`
`5.4. Modular Structure of Hierarchical
`Network Topology .
`.
`.
`.
`.
`.
`.
`
`5.5. Hierarchical Network Topology
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`5.6.
`
`031 Reference Model vs. Proposed Protocol
`Architecture 0
`I
`O
`0
`I
`I
`O
`C
`C
`C
`C
`I
`I
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`I
`
`5.7.
`
`Expanded Definition of the Proposed Protocol
`Architecture .
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`
`5.8.
`
`Frame Structure
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`5.9.
`
`Preamble and Guard Band Fields
`of a Frame .
`.
`.
`.
`.
`.
`.
`.
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`Page
`
`157
`
`155
`
`177
`
`184
`
`186
`
`188
`
`190
`
`19”
`
`197
`
`205
`
`207
`
`5.10. Start Delimiter Field of a Frame .
`
`5.11. Control Field of a Frame .
`
`.
`
`.
`
`5.12. Frame Number Field of a Frame
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`5.13. Frame Check Sequence Field of a Frame
`
`5.1”. Subframe and Super Subframe Structure
`
`5.15. Start Delimiter of a Subframe
`
`5.16. Control Field of a Subframe
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`5.17. Source and Destination Address Fields
`of a Subframe
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`
`5.18. Data Field of a Subframe .
`
`.
`
`5.19. Subframe Check Sequence Field
`of a Subframe
`.
`.
`.
`.
`.
`.
`
`.
`
`.
`
`.
`
`.
`
`5.20. Guard Band Field of a Subframe .
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`208
`
`209
`
`211
`
`212
`
`21H
`
`215
`
`216
`
`218
`
`218
`
`219
`
`220
`
`ix
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 13
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 13
`
`

`

`Figure
`
`5.21. Installation Packet Format
`
`.
`
`.
`
`.
`
`.
`
`.
`
`5.22. Network/Station Status Packet Format
`
`5.23. Acknowledgment Packet Formats
`
`5.24. Reservation Packet Formats .
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`5.25. Datagram, Statically-Reserved, and
`Dynamically-Reserved Packet Formats
`
`5.26. Propagation Delay Definition .
`
`5.27. Propagation Delay Effect on
`Synchronization
`.
`.
`.
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`5.28.
`
`Implementation of Latency Adjustment
`
`Page
`
`221
`
`222
`
`223
`
`225
`
`225
`
`228
`
`230
`
`23H
`
`237
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`I
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`I
`
`5.29. Frame Synchronization and Subframe
`slotting D
`I
`I
`O
`O
`l
`O
`O
`O
`I
`I
`I
`
`I
`
`l
`
`I
`
`5.30. Source and Destination Address Formats .
`
`5.31. Frame Header Format of Statically
`Reserved Frame Slot
`.
`.
`.
`.
`.
`
`5.32. Frame Header Format of Statically
`Reserved Subframe Slots
`.
`.
`.
`
`.
`
`.
`
`5.33. Frame Header Format of Dynamically
`Reserved Frame Slot
`.
`.
`.
`.
`.
`.
`
`5.3a. Frame Header Format of Dynamically
`Reserved Subframe Slots
`.
`.
`.
`.
`
`5.35. Random Number Generator
`
`.
`
`.
`
`.
`
`.
`
`5.36. Random Frame and Subframe Number
`Generation .
`.
`.
`.
`.
`.
`.
`.
`.
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`5.37. Randomly Distributed Retry Algorithm .
`
`5.38. Multi-Mode Media-Access Protocol
`State Diagram .
`.
`.
`.
`.
`.
`.
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`2fl0
`
`249
`
`258
`
`269
`
`277
`
`289
`
`289
`
`295
`
`300
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 14
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 14
`
`

`

`LIST OF ABBREVIATIONS AND SYMBOLS
`
`Abbreviation
`
`Term
`
`AP
`
`ATDMA
`
`BEE
`
`Alternating Priorities
`
`Asynchronous Time-Division Multiple
`Access
`
`Bit Error Rate
`
`BRAM
`
`'
`
`Broadcast Recognizing Access Method
`
`CAD
`
`CATV
`
`Computer Aided Design
`
`Community Antenna Television
`
`CDMA
`
`‘
`
`Code-Division Multiple Access
`
`CPODA
`
`GSMA
`
`GSMA/CD
`
`FDM
`
`FDMA
`
`FPODA
`
`FSK
`
`GSMA
`
`ISDN
`
`ISO
`
`LAN
`
`LLC
`
`MAN
`
`MLMA
`
`031
`
`PBX
`
`Contention Priority-Oriented
`Demand Assignment
`
`Carrier Sense Multiple Access
`
`Carrier Sense Multiple Access with
`Collision Detection
`
`Frequency—Division Multiplexing
`
`Frequency-Division Multiple Access
`
`Fixed Priority-Oriented Demand
`Assignment
`
`Frequency Shift Keying
`
`Global Scheduling Multiple Access
`
`Integrated Services Digital Network
`
`International Standards Organization
`
`Local Area Network
`
`Logical Link Control
`
`Metropolitan Area Network
`
`Multi-Level Multiple Access
`
`Open System Interconnection
`
`Private Branch Exchange
`
`xi
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 15
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 15
`
`

`

`Abbreviation
`
`Term
`
`P-CSMA
`
`P—CSMA/CD
`
`Prioritized Carrier Sense Multiple
`Access
`
`Prioritized Carrier Sense Multiple
`Access with Collision Detection
`
`PDN
`
`PDU
`
`PSK
`
`RF
`
`R0
`
`RR
`
`SDU
`
`STDMA
`
`TDM
`
`TDMA
`
`TTL
`
`VLSI
`
`Public Data Network
`
`Protocol Data Unit
`
`Phase Shift Keying
`
`Radio Frequency
`
`Random Order.
`
`Round Robin
`
`Service Data Unit
`
`Synchronous Time-Division Multiple
`Access
`
`Time—Division Multiplexing
`
`Time-Division Multiple Access
`
`Transistor-Transistor Logic
`
`Very Large System Integration
`
`VT-CSMA
`
`Virtual—Time Carrier Sense Multiple
`Access
`
`xii
`
`Petitioner Cisco Systems - Exhibit 1014 - Page .16
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 16
`
`

`

`ABSTRACT
`
`Several media-access protocols have been proposed and
`implemented for packet-switching networks including
`
`Satellite, Radio, and Local Area Networks. The protocols
`
`employed in these packet-switching retworks are mainly
`
`intended and tailored for certain applications such as data
`
`and multiplexed voice. With the emergence of Metropolitan
`Area Networks (MANs) using coaxial cable and fiber optics
`
`cable as a transport medium,
`
`a new media-access protocol
`
`is
`
`needed to offer integrated services such as data, packetized
`
`voice,
`
`and digitized video over a single shared channel.
`
`This dissertation proposes a new media-access protocol
`
`and communication network topology for MANs. This protocol
`
`will support data, packetized voice and digitized/compressed
`
`video services. The scope of this dissertation also includes
`
`the definition and characterization of Metropolitan Area
`
`Networks encompassing network topologies, properties, and
`
`service requirements.The mediafaccess protocols intended
`
`for Satellite, Radio, and Local Area Networks are summarized
`
`and vigorously scrutinized as applied to Metropolitan Area
`
`Networks.
`
`xiii
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 17
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 17
`
`

`

`CHAPTER I
`
`INTRODUCTION
`
`1.1 Evolution of Media-Access Protocols
`
`The rapidly declining cost of communication links makes
`
`it more economical
`
`to access specialized resources at
`
`their
`
`source rather than making hardware and software available at
`
`each user site. Packet-switched networks have emerged as the
`
`main transport mechanism for
`
`a variety of services ranging
`
`from transmission of data and voice to
`
`the delivery of
`
`digitized images and graphics. Packet switching is a
`
`reapplication of the basic dynamic allocation techniques
`
`used for over a century by the mail and telegraph systems
`
`[KUO 811.‘ Packet switching can readily adapt
`
`to a wide
`
`range of user services and user demands because it permits
`
`communication resources to be used at utmost efficiency.
`
`Presently, packet switching is primarily being used in
`
`connection with computer
`
`and data communications. However,
`
`its effectiveness for digitized voice and video, and other
`
`wideband communication services has demonstrated that
`
`this
`
`technique will undoubtedly become a "de facto" standard for
`
`integrated service networks [ROSN 82].
`
`The speed and volume requirements of the data traffic
`
`created by the advent of desk-top computers and distributed
`
`!
`
`Numbers in parentheses refer to numbered references in the
`
`bibliography.
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 18
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 18
`
`

`

`computing devices are beginning to overflow the conventional
`
`circuit-switching telephone network [COOK 8”]. 0n the other
`
`hand,
`
`the transmission and processing of voice and video
`
`signals is shifting towards the digital arena [MOKH 8B].
`
`For example, digital PBXs are being designed to serve as
`
`local area networks to support voice and data services
`
`simultaneously. It
`
`is perceived that
`
`the integration of
`
`these services, data, voice and video, over
`
`a single medium
`
`shared among thousands of users would be the most economical
`
`and feasible solution [MAZU 83, MASO 83, RITC 83]. However,
`
`an arbitration mechanism, namely a media-access protocol
`
`is
`
`required to support all these services which have different
`
`requirements. Specifically,
`
`the degree of throughput-delay-
`
`stability tradeoffs for the media-access protocols may vary
`
`considerably such that one media-access protocol may not
`
`meet all application requirements.
`
`In addition,
`
`the
`
`performance of
`
`a multiple access protocol,
`
`in which
`
`conflicts are resolved through a certain method, is strongly
`
`dependent on the traffic model
`
`and network loading.
`
`In
`
`general,
`
`some traffic characteristics do favor one class of
`
`protocols more than the others.
`
`Since the development of packet-switched radio networks
`
`in the early 703, there have been significant advances in
`
`data communications,
`
`specifically in high speed local area
`
`networks, LANs utilizing coaxial cable as
`
`a shared medium.
`
`The majorityof LANsserve ageographicalarea ofone totwo
`
`miles and mainly carry only one signal and generally provide
`
`high speed data transmission.
`
`In order
`
`to transmit signals
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 19
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 19
`
`

`

`over
`
`long distances the signal must be modulated,
`
`i.e., use
`
`a broadband medium. The broadband medium can carry multiple
`
`signals by using frequency division multiplexing on the same
`
`medium. Advantages of a broadband system include: allocation
`
`of bandwidth on demand, simultanenous transmission of data,
`
`voice and live video, high capacity of signalling rates,
`
`mass-produced cable and shared expenses. Examples range from
`
`a city,
`
`in which thousands of buildings and houses are tied
`
`into one wide area
`
`network [MCNA 83], also called
`
`Metropolitan Area Network MAN,
`
`through a university campus,
`
`in which thousands of dormitory rooms,
`
`labs, offices and up
`
`to several hundreds of buildings are connected via a single
`
`MAN [SHIP 82],
`
`to a company
`
`occupying a
`
`few buildings
`
`scattered across a
`
`large
`
`geographical area [MAZU 83]. LANs
`
`serve users in a limited geographical area, up to a couple
`
`of miles, whereas Long Haul Networks serve users that are
`
`hundreds or thousands of miles apart. Nonetheless, a long
`
`haul network,
`
`in other words a global network, can be formed
`
`by interconnecting several MANs
`
`through gateways or bridges.
`
`In the last couple of years, LANs have been extended to
`
`cover
`
`larger geographical areas up to 10 kilometers in
`
`radius.
`
`In order
`
`to span over
`
`such a distance the same
`
`media-access protocols with some performance tradeoffs are
`
`being employed
`
`over
`
`a broadband medium [ENNI 83]. However,
`
`it is unlikely that these protocols would perform as well
`
`over
`
`a broadband medium as over
`
`the baseband medium for
`
`which they were originally intended.
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 20
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 20
`
`

`

`The permanent
`
`and virtual circuit-switching technique
`
`with store-and-forward capabilities is most commonly used in
`
`long haul networks where the flow control
`
`and routing
`
`problems are addressed rather
`
`than media-access protocols.
`
`These networks mainly support the bulk of point—to-point
`
`data traffic across the ILS.A.
`
`through the circuit-switched
`
`telephone network operating at the maximum of 56 kilobits
`
`per
`
`second. The operational
`
`range of
`
`these networks is
`
`extended around the globe via satellites. The present global
`
`network architecture does not
`
`require a media-access
`
`protocol,
`
`rather point-to-point communication links are
`
`established to provide full—interconnection among network
`
`nodes.
`
`In satellite networks the frequency-division (FDM)
`
`and
`
`time-division multiplexing (TDM)
`
`techniques are commonly
`
`used. In general terms, a fixed-bandwidth is assigned to a
`
`single user or
`
`a certain portion of
`
`the bandwidth is
`
`allocated to multiple users on a demand basis. However,
`
`these networks generally support up to two hundred users
`
`that have heavy and continuous traffic requirements. The
`
`most typical property of Satellite Networks is that the one-
`
`way signal propagation delay is in the range of 125
`
`milliseconds,
`
`therefore, LANs media-access protocols such as
`
`CSMA/CD, Token-Bus, etc., cannot be employed efficiently. If
`
`the traffic between two points is regular and continuous,
`
`Frequency-Division Multiple Access (FDMA) scheme performs
`
`very efficiently.
`
`In this technique network nodes
`
`communicate via carrier signals on which message signals are
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 21
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 21
`
`

`

`modulated as in radio and TV transmission. For point-to-
`
`point communications one or more channels are fixed-
`
`assigned. For multiple users sharing a
`
`frequency spectrum,
`
`each channel may be subdivided into an arbitrary number of
`
`subchannels that are dynamically allocated on a demand
`
`basis.
`
`The Time—Division Multiple Access (TDMA) scheme
`
`performs well with user devices that have very regular
`
`information transfer requirements,
`
`in a high—duty cycle,
`
`since it
`
`can sustain high signalling rates under
`
`those
`
`conditions. However,
`
`there are some instances where TDMA may
`
`not meet
`
`information transfer requirements,
`
`therefore,
`
`further
`
`frequency-multiplexing may be needed before time-
`
`division is applied.
`
`In other words, TDMA is superimposed on
`
`the elementary FDM.
`
`In the Reservation—TDMA scheme for satellite networks
`
`the channel is subdivided into multiple time slots. These
`
`slots are dynamically allocated on a demand basis. The
`
`reservation schemes are inevitably inefficient when network
`
`traffic load is low, and reserved slots will not be used for
`
`long periods of
`
`time between transmission bursts. However,
`
`if the time slots can be reallocated dynamically and if
`
`empty slots can be removed effectively,
`
`then the throughput
`
`can be improved. For
`
`those applications where guaranteed
`
`response time, high performance and stability are important,
`
`the reservation TDMA scheme with dynamic control would be
`
`ideal.
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 22
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 22
`
`

`

`In packet-switched radio networks the following media-
`
`access protocols are used with limited efficiency:
`
`1) Pure-
`
`Aloha, 2) Slotted-Aloha. 3) OSHA, and u) Round-Robin with
`
`various priority schemes. All of
`
`these protocols are
`
`optimized specifically for bursty interactive data traffic
`
`such as terminal-to-computer, computer-to-computer, etc.
`
`In
`
`general
`
`terms, packet-switched radio networks
`
`serve a
`
`geographical area maximum of one or two hundred miles in
`
`radius,
`
`and the number of users supported on the network
`
`does not exceed a couple of hundred users.
`
`The best media-access protocols for Metropolitan Area
`
`Networks,
`
`in which the signal propagation delay is
`
`inherently large, are not necessarily the same as for Local
`
`Area Networks which are optimized for specific applications
`
`and distances of a mile or two in cable length. The longer
`
`propagation delay of signals in MAN means that an extremely
`
`high price must be paid in data rate or efficiency if other
`
`parameters are unchanged. Several different media-access
`
`protocols have been developed for LANs by which a couple of
`
`hundred users are supported for one specific application,
`
`mainly data transmission.
`
`In Carrier Sense Multiple Access with Collision
`
`Detection, CSMA/CD scheme, collision detection depends on
`
`the mutilated data packets existing anywhere on the medium
`
`[P803 85]. Therefore,
`
`the packet
`
`transmission time must be
`
`at
`
`least
`
`twice the maximum signal propagation time. Unless
`
`the packet size is made excessively long, an extension of
`
`the transmission system by a factor of X results in a speed
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 23
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 23
`
`

`

`reduction by a factor of X.
`
`In order to obtain the same
`
`throughput, given that
`
`the packet size is kept
`
`the same the
`
`data rate must be reduced by a factor proportional to the
`
`system size, otherwise there is considerable throughput
`
`degradation. Moreover,
`
`in wide area networks covering large
`
`geographical areas the collision detection is a much more
`
`difficult
`
`task than LANs. Generally, CSMA/CD provides very
`
`fast
`
`response under
`
`light
`
`load condition and sustains very
`
`good efficiency. Since it is a statistical method, as the
`
`load increases the average delay may exceed a threshold that
`
`is defined for proper packetized voice transmission,
`
`thus
`
`preventing the transmission of voice traffic [BRUT 83]. The
`
`stability characteristic of CSMA/CD protocol due to its non-
`
`deterministic nature should also be considered in certain
`
`applications such as digitized voice traffic, etc., where
`
`instability and delay variance cannot be tolerated. CSMA/CD
`
`provides no limit on the number of packets that can be
`
`transmitted between successive transmission rights given to
`
`a network station. That is, it has no intrinsic mechanism
`
`for guaranteeing a certain portion of the bandwidth to any
`
`station. However,
`
`if extrinsic restrictions are imposed on
`
`demands,
`
`then a certain amount of the bandwidth may be
`
`guaranteed for any station,
`
`in turn limiting the maximum
`
`packet
`
`length and requiring additional rules for higher
`
`level protocols to limit packet
`
`transmission rates. But this
`
`turns the system into a voice only network where bandwidth
`
`is allocated in small
`
`increments for long periods of time.
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 24
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 24
`
`

`

`In the Token-Bus media-access protocol,
`
`a
`
`token is
`
`circulated to all nodes on the network, whether they have
`
`anything to send or not
`
`[P804 82]. Therefore,
`
`too much time
`
`is wasted by passing the token to all users in MAN where the
`
`propagation delay is quite large and the token must travel
`
`to the headend and then transmitted back in the forward
`
`direction. This scheme is also very sensitive to the number
`
`of users sharing the medium. As
`
`the number of users
`
`increases the average delay will also increase
`
`proportionally.
`
`In addition,
`
`the recovery procedures needed
`
`for lost-token conditions may be very complicated in MAN
`
`environment. Nonetheless,
`
`token-passing schemes,
`
`in general,
`
`behave well under
`
`load but
`
`introduce longer delays than
`
`CSMA/CD under
`
`light
`
`load [BRUT 83]. Since the token-passing
`
`schemes are deterministic,
`
`the average delay can be
`
`predicted, allowing easy handling of voice traffic,
`
`and the
`
`stability of the protocol is not an issue to be concerned
`
`with.
`
`Token-Bus protocol also intrinsically provides a
`
`guaranteed bandwidth. That is,
`
`the worst case access time
`
`delay between transmissions for
`
`a given network station is
`
`determined by the time it takes all other stations to send
`
`maximum—size packets. 0n the other hand,
`
`the best access
`
`time delay is defined as
`
`the time between successive
`
`transmissions by a given station plus the time for the token
`
`to pass through all stations. Nonetheless, propagation on
`
`the medium adds at least 2T/N per station, where T is the
`
`one-way end—to-end signal propagation time for the medium
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 25
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 25
`
`

`

`and N represents the number of stations. Since the signal
`
`propagation delay of wide area networks is inherently large,
`
`the token—bus protocol performance would degrade
`
`drastically.
`
`In the token-passing ring protocol,
`
`a station can start
`
`sending a
`
`token almost
`
`immediatelly after it starts
`
`receiving it.
`
`In a
`
`ring configuration,
`
`the delay for
`
`a
`
`station to decode the incoming physical signals, recognize a
`
`token, decide whether to change it to a start of frame,
`
`and
`
`re-code an outgoing signal stream can be kept minimal and
`
`this delay is relatively independent of the bit rate of the
`
`ring [P805 85]. Since this
`
`scheme allows much more time
`
`spent for data transmission rather than propagating the
`
`token, it can be considered for the integration of voice and
`
`data on the same shared channel. However, as the number of
`
`network users increases,
`
`the average delay will increase
`
`proportionally. For
`
`those networks covering a
`
`large
`
`geographical area,
`
`a break between any stations or any
`
`station failure on
`
`the ring will disrupt
`
`the network
`
`operation. Due
`
`to its topological ramifications,
`
`the token
`
`passing ring protocol may not be applicable to MANs.
`
`A major difference between MANs and LANs is that LANs
`
`are owned by the same private organizations,
`
`therefore,
`
`no
`
`billing and control
`
`issues exist. 0n the other hand, MAN is
`
`considered a Public Network,
`
`in turn requiring centralized
`
`control of maintenance and billing. These functions are not
`
`provided by the peer—to-peer protocols used for LANs.
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 26
`
`Petitioner Cisco Systems - Exhibit 1014 - Page 26
`
`

`

`10
`
`1.2 Emergence of Metropolitan Area Networks
`
`A digital communication network serving a metropolitan
`
`area with a
`
`radius of one to twenty miles is called a
`
`Metropolitan Area Network, MAN. It is a compromise between
`
`Long Haul Networks like ARPANET, TYMNET, SATNET, TELENET,
`
`etc., and Local Area Networks like ETHERNET, CHEAPERNET,
`
`TOKEN-RING, STARLAN, NET/ONE, LOCALNET/BO, MITRENET, etc.
`
`Communication media for MANs
`
`include broadband coaxial
`
`cable, fiber optics and radio.
`
`By providing the capability of transmitting signals
`
`over long distances via fiber optics cable, coaxial cable,
`
`or radio transport media, the distribution, retrieval and
`
`exchange of digital
`
`information in any form in large
`
`geographical areas is made possible. The salient motivation
`
`for MANs is the desire to reduce the average costs to many
`
`distributed users by using intelligent components in the
`
`commun