United States Patent [19J
`Drake, Jr.; et al.
`
`[54] QUALITY OF SERVICE MANAGEMENT
`FOR SOURCE ROUTING MULTIMEDIA
`PACKET NETWORKS
`
`[75]
`
`Inventors: John E. Drake, Jr., Pittsboro;
`Elizabeth A. Hervatic, Cary; Joseph
`W. Pace, Cary; Ralph J. Potok, Cary;
`David E. Taber, Wake Forest, all of
`N.C.
`
`[73] Assignee: International Business Machines
`Corporation, Armonk, N.Y.
`
`[21] Appl. No.: 255,219
`
`[22] Filed:
`
`Jun. 7, 1994
`
`Int. Cl.6
`...................•................................. H04Q 11/00
`[51]
`[52] U.S. Cl . ............................... 370/54; 370/17; 370/94.1
`[58] Field of Search ............................... 370/54, 94.1, 60,
`370/85.5, 85.6, 85.7.85.13, 94.3, 13, 17
`
`[56]
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`I 1111111111111111 11111 111111111111111 IIIII IIIII IIIII IIIII 111111111111111111
`US005461611A
`[11] Patent Number:
`[45] Date of Patent:
`
`5,461,611
`Oct. 24, 1995
`
`5,347,511
`5,359,593
`5,361,256
`5,388,097
`
`9/1994 Gun ........................................... 370/54
`10/1994 Derby et al ............................ 370/94.1
`11/1994 Doeringer et al .................... 370/85.13
`2/1995 Baugher et al ........................ 370/85.5
`
`Primary Examiner-Douglas W. Olms
`Assistant Examiner-Shick Hom
`Attorney, Agent, or Firm-Robert 0. Nimtz
`
`[57]
`
`ABSTRACT
`
`A management system for local area networks ensures
`selected levels of quality of service to all transmission
`requests submitted to the management system. This man(cid:173)
`agement system is attached to the network and receives
`requests from all other stations on the network to reserve
`facilities for a particular quality of service data stream. An
`allocator in the management system determines if the
`requested facilities are available and, if so, reserves these
`facilities for the requesting station. If the facilities are not
`available, the request is denied. A hierarchical data base
`containing all of the current parameters of all of the network
`resources and all of the currently supported data streams is
`used to support the allocation process.
`
`4,858,232
`
`8/1989 Diaz et al. ................................ 370/60
`
`24 Claims, 10 Drawing Sheets
`
`r-----------------------------, r-----------------------------,
`'
`. - - - - - ,
`'
`'
`: SOURCE APPLICATION
`: TARGET APPLICATION
`: STATION REQUESTING
`STATION RECEIVING
`QoS
`:
`DATA STREAM
`
`11
`QoS
`•
`QoS
`REQUESTOR: PROTOCOL
`MANAGER
`: MACHINE
`12
`TRANSPORT
`PROTOCOL
`STACK
`
`13
`
`15
`
`26
`
`TRANSPORT
`PROTOCOL
`STACK
`
`27
`
`-----------'-10 L-------------- -----------'-29
`
`LAN
`
`17
`r--------------- ---------------,
`' ' ' '
`
`TRANSPORT
`PROTOCOL
`STACK
`
`22
`QoS
`•
`QoS
`REQUESTOR: PROTOCOL
`MANAGER
`: MACHINE
`23
`
`24
`
`QoS
`ALLOCATION
`DATA BASE
`
`25
`L--------------------•-••---• '--20
`
`Samsung Ex. 1006
`Page 1
`
`

`

`U.S. Patent
`
`Oct. 24, 1995
`
`Sheet 1 of 10
`
`5,461,611
`
`FIG. 1
`;-----------------------------~ ;-----------------------------~
`SOURCE APPLICATION
`TARGET APPLICATION
`STATION REQUESTING
`STATION RECEIVING
`QoS
`DATA STREAM
`
`11
`QoS
`PROTOCOL
`MACHINE
`
`13
`
`QoS
`REQUESTOR:
`MANAGER !
`12
`TRANSPORT
`PROTOCOL
`STACK
`
`26
`
`TRANSPORT
`PROTOCOL
`STACK
`
`15
`
`27
`
`I
`.I
`I
`
`I
`
`L--------------
`
`I
`
`L-------------- - - - - - - - -- - - -\..29
`
`____ __,
`
`LAN
`
`17
`;--------------- ---------------~
`QoS
`ALLOCATOR M
`
`I
`
`TRANSPORT
`PROTOCOL
`STACK
`
`QoS
`REQUESTOR:
`MANAGER
`:
`
`22
`QoS
`PROTOCOL
`MACHINE
`
`23
`
`24
`
`QoS
`ALLOCATION
`DATA BASE
`
`25
`----------------------------'-20
`
`I
`
`Samsung Ex. 1006
`Page 2
`
`

`

`U.S. Patent
`
`Oct. 24, 1995
`
`Sheet 2 of 10
`
`5,461,611
`
`I
`
`BRIDGE
`
`'-31
`
`FIG. 2
`
`ALLOCATOR
`
`'-30
`
`,32
`
`SEGMENT
`
`REQUESTOR
`
`I
`LAN
`A. TT ACHMENT~
`
`I
`BRIDGE
`ATTACHMENT
`
`'-33
`
`QoS
`STREAM
`
`'-35
`
`'-36
`
`'- 42
`
`FIG. 3
`
`HEADER
`
`ROUTING SOURCE DEST.
`TRAFFIC
`QoS
`QoS
`FIELDS ADDRESS ADDRESS DESCRIPTORS DESIRED ACCEPTABL
`
`'-50
`
`'-51
`
`'-52
`
`'-53
`
`'-54
`
`'-55
`
`'-56
`
`Samsung Ex. 1006
`Page 3
`
`

`

`U.S. Patent
`
`Oct. 24, 1995
`
`Sheet 3 of 10
`
`5,461,611
`
`FIG. 4
`
`r---------
`
`START
`
`60
`
`SOURCE
`SENDS
`EG.REQUES
`
`61
`
`EGISTRATIO
`RECEIVED AT
`ALLOCATOR
`
`62
`SAVE MAC
`ADDRESS
`AND REPLY
`
`63
`
`CONFIRM
`EGISTRATIO
`
`65
`---------.J
`
`I
`
`TARGET
`REQUESTS ·
`FILE LIST
`
`66
`
`SOURCE
`SENDS
`FILE LIST
`
`67
`
`TARGET
`DISPLAYS
`FILE LIST
`
`68
`
`USER
`SELECTS
`FILE
`
`69
`
`SOURCE
`RECEIVES
`SELECTION
`
`70
`
`SOURCE
`REQUESTS
`ALLOCATION
`
`71
`
`DETERMINE
`COMPONENTS
`IN ROUTE
`
`FIG. 5
`
`72
`
`\...73
`
`Samsung Ex. 1006
`Page 4
`
`

`

`U.S. Patent
`
`Oct. 24, 1995
`
`Sheet 4 of 10
`
`5,461,611
`
`FIG. 5
`
`INITIALIZE:
`DELAY=0
`BANDWIDTH=OK
`
`81
`
`NO
`
`RETRIEVE
`NEXT
`COMPONENT
`
`83
`
`SEARCH
`FOR
`COMPONENT
`
`NO
`
`UPDATE
`COMPONENTS
`IN DATA BASE
`94
`
`CREATE
`aos STREAM
`OBJECT
`
`95
`
`SEND
`ALLOCATION
`ACCEPTANCE
`
`.INCREMENT
`DELAY
`
`EXAMINE
`BANDWIDTH
`AVAILABLE
`
`SEND
`ALLOCATION
`DENIAL
`
`RECEIVE
`96
`...._ ____ ~ ALLOCATION _____ ___.
`MESSAGE
`
`92
`
`SEND
`FILE TO
`TARGET
`
`SEND
`DENIAL TO
`TARGET
`
`100
`
`Samsung Ex. 1006
`Page 5
`
`

`

`U.S. Patent
`
`Oct. 24, 1995
`
`Sheet 5 of 10
`
`5,461,611
`
`FIG. 6
`
`START
`
`110
`
`SENDER
`REQUESTS
`DEALLOCATE
`
`111
`
`DEALLOCATE
`RECEIVED AT
`ALLOCATOR
`
`112
`
`SEARCH
`DATA BASE
`FOR STREAM
`
`113
`
`NO
`
`NO
`
`114
`YES
`EXTRACT
`COMPONENT
`LIST
`
`IGNORE
`REQUEST
`
`ADJUST BY
`ALLOCATED
`VALUE
`
`ERROR
`REPLY TO
`SENDER
`
`115
`
`117
`
`121
`
`122
`
`DONE
`
`123
`
`GET NEXT
`ITEM
`ON LIST
`
`NO
`
`Samsung Ex. 1006
`Page 6
`
`

`

`U.S. Patent
`
`Oct. 24, 1995
`
`Sheet 6 of 10
`
`5,461,611
`
`FIG. 7
`
`START
`
`130
`RECEIVE
`INCREASE BW
`REQUEST
`
`131
`EXAMINE
`STREAM
`ID
`
`132
`
`SEARCH
`DB FOR
`STREAM ID
`
`UPDATE
`DATABASE
`
`141
`INCREASE BW
`GRANTED
`SENT
`
`134
`
`DONE
`135
`
`INCREASE BW
`DENIAL
`SENT
`
`138
`
`DONE
`139
`
`Samsung Ex. 1006
`Page 7
`
`

`

`U.S. Patent
`
`Oct. 24, 1995
`
`Sheet 7 of 10
`
`5,461,611
`
`FIG. 8
`
`START
`150
`RECEIVE
`REDUCE BW
`REQUEST
`151
`RETRIEVE
`ITEM
`LIST
`
`152
`
`SEEK
`NEXT ITEM
`ON LIST
`
`DONE
`155
`
`NO
`
`NO
`
`UPDATE
`ITEM
`BANDWIDTH
`154
`
`ECREASE B
`DENIAL
`SENT
`
`158
`
`DONE
`
`159
`
`Samsung Ex. 1006
`Page 8
`
`

`

`U.S. Patent
`
`Oct. 24, 1995
`FIG. 9
`
`Sheet 8 of 10
`
`5,461,611
`
`START
`160
`RECEIVE
`REDUCTION
`REQUEST
`
`161
`INITIALIZE
`DELAY
`AT ZERO
`
`177
`RETRIEVE
`ITEM
`LIST
`
`162
`
`NO
`
`REDUCTION
`DENIAL
`SENT
`
`172
`
`DONE
`
`173
`
`NO
`
`REDUCTION
`GRANTED
`SENT
`
`134
`
`DONE
`165
`
`NO
`
`REDUCTION
`DENIAL
`SENT
`
`168
`
`SEEK
`NEXT ITEM
`ON LIST
`
`INCREMENT
`TOTAL
`DELAY
`
`170
`
`Samsung Ex. 1006
`Page 9
`
`

`

`U.S. Patent
`
`Oct. 24, 1995
`
`Sheet 9 of 10
`
`5,461,611
`
`FIG. 10
`
`START
`
`180
`
`REGISTER
`REQUESTOR
`
`181
`
`RECEIVE
`ALLOCATON
`REQUEST
`182
`ALLOCATION
`GRANT
`RECEIVED
`
`183
`
`START
`REFRESH
`TIMER(R)
`
`184
`
`REFRESH
`TIMER(R)
`EXPIRES
`
`186
`REQUESTOR
`SENDS
`REFRESH
`
`187
`RESTART
`REFRESH
`TIMER(R)
`
`188
`
`REFRESH
`MESSAGE
`RECEIVED
`
`189
`
`RESET
`ASR
`COUNTER
`
`190
`
`DONE
`191
`
`Samsung Ex. 1006
`Page 10
`
`

`

`U.S. Patent
`
`Oct. 24, 1995
`
`Sheet 10 of 10
`
`5,461,611
`
`FIG. 11
`
`START
`200
`BRING
`UP
`SYSTEM
`
`201
`
`START
`REFRESH
`TIMER(A)
`202
`
`REFRESH
`TIMER(A)
`EXPIRES
`
`204
`
`NO
`
`DONE
`
`207
`
`GET NEXT
`STREAM
`OBJECT
`
`208
`INCREMENT
`ASR
`COUNTER
`
`NO
`
`DEALLOCATE
`RESOURCES
`(FIG. 6)
`
`211
`
`Samsung Ex. 1006
`Page 11
`
`

`

`5,461,611
`
`1
`QUALITY OF SERVICE MANAGEMENT
`FOR SOURCE ROUTING MULTIMEDIA
`PACKET NETWORKS
`
`TECHNICAL FIELD
`
`This invention relates to multimedia packet transmission
`systems and, more particularly, to insuring adequate quality
`of service (QoS) for transmission of multimedia signals in
`local area networks.
`
`BACKGROUND OF THE INVENTION
`
`Multimedia applications are computer programs that pro(cid:173)
`vide the capability to generate, transport, and present infor(cid:173)
`mation in textual, graphic, aural and visual formats. In many
`multimedia applications, information is generated or stored
`at devices that are remote from the using devices and human
`users. In such situations, a communications network must
`provide the transport mechanisms to users in a timely and
`efficient manner. Multimedia information, particularly audio
`and full motion video, has unique properties that impose
`stringent requirements on the communications network.
`Unexpected network delays caused by throughput or pro- 25
`cessing delays can disrupt the presentation of the multimedia
`data to the end user. An analogy would be trying to carry on
`a telephone conversation when the network introduced inter(cid:173)
`mittent pauses, delays or slowdowns in the voice stream.
`Examples of multimedia application that put an emphasis on 30
`the network are Client/Server playback of stored multimedia
`data streams (e.g., library distribution), Client/Client video
`conferencing, and Client/Client collaborative work.
`The property of multimedia information that most sig(cid:173)
`nificantly affects requirements of the underlying network is
`the high bandwidth needed to transmit video data, coupled
`with the requirement of isochronous transmission, that is,
`the information must be presented to the user in real time
`and pace. The playback of full-screen, high-quality, stored
`video and audio at the standard rate of thirty video frames
`per second; even when compressed, requires approximately
`1.2 megabits per second of bandwidth. Four megabits per
`second or more are required to support two-way video
`(interactive or conferencing) of high quality. In addition to
`the high bandwidth requirements, the network must assure 45
`that the data is delivered with (a priori) bounded delay. Some
`communications technologies, particularly time division
`multiplexing (TDM), are ideally suited to meeting these
`high bandwidth and bounded delay requirements. Unlike
`TDM networks, however, packet or cell based networks do 50
`not inherently guarantee the delivery of a specified quantity
`of data in each time interval of a specified duration. There~
`fore, a method is required in those packet networks to
`provide equivalent levels of network service for the multi(cid:173)
`media applications. This function can be called bandwidth 55
`management, or more broadly, quality of service (QoS)
`management.
`Emerging high bandwidth, packet and cell based tech(cid:173)
`nologies and architectures (e.g., B-ISDN) anticipate this
`requirement and thus incorporate techniques to accomplish 60
`quality of service management. These techniques typically
`involve the provision of a sophisticated user network inter(cid:173)
`face through which the user requests a connection for
`multimedia transport and specifies the quality of service that
`is required. Within the network itself, sophisticated algo- 65
`rithms are provided to examine the status of resources,
`compute a route that best satisfies the request, reserve those
`
`5
`
`2
`resources, and notify the user that the connection has been
`reserved. These algorithms are expensive to implement and
`are among the most technically demanding functions within
`the network. They typically require the network to under-
`stand the capacity and delay characteristics of each com(cid:173)
`munications link in the network in order to determine
`whether the quality of service request can be granted. In
`addition, they require the network to establish, maintain, and
`update the global network topology information data base in
`10 order to determine the optimal route for a connection Most
`packet based local area networks (LANs), such as token
`rings (IEEE Standard 802.5), do not offer these sophisticated
`techniques for quality of service management.
`It is extremely desirable to provide apparatus and a
`15 method to control multimedia data stream entry into a LAN,
`based on the quality of service requirements for that par(cid:173)
`ticular data stream and the quality of service available in the
`LAN. The intent of such a technique is to deny network
`access to those streams whose level of quality of service
`20 requirements are not currently available in the LAN net(cid:173)
`work.
`
`SUMMARY OF THE INVENTION
`
`35
`
`In accordance with the illustrative embodiment of the
`present invention, multimedia data streams are managed in
`a local area network (LAN), or in a bridged LAN environ(cid:173)
`ment, by identifying all of the network components in the
`LANs and bridges which participate in a data path between
`a user of the LAN and a source of multimedia information.
`The quality of service parameters that describe the QoS
`available in each network component resource are deter(cid:173)
`mined dynamically or statically, stored in predetermined
`parameter stores, and used at the time a request for an
`allocation of resources is made for a multimedia transmis(cid:173)
`sion. When such a request is made, the stored component
`parameters are consulted to determine if the components in
`the selected path, individually and together, satisfy the
`40 requested QoS values for a multimedia transmission. If so,
`the request is granted. If not, the request is denied.
`In accordance with one feature of the present invention,
`the Routing Information Field (RIF), already available in
`such networks for source routing of frames through bridged
`LANs, as taught in Section 10.3.7.3 of ISO/IEC 8802-2
`PDAM 5.3, August, 1992, is used to determine the path
`components. As is well known, the RIF is a series of
`segment numbers and bridge numbers that identify the
`network components which a frame traverses en route from
`a source to a destination. Such a RIF is constructed in the
`prior art at the time the multi-media data stream sender and
`receiver establish a "session" (e.g., using a telecommunica(cid:173)
`tions protocol such as Net BIOS) over which the data stream
`is to flow. The availability of an already constructed speci(cid:173)
`fication of the path components significantly reduces the
`complexity of the QoS LAN access system of the present
`invention. A major advantage of the present invention is the
`ability to provide quality of service management in bridged
`LAN environments using all of the existing connection
`set-up procedures, thereby providing such QoS management
`with little added complexity. It is possible, of course, to
`create in the QoS management system a route selection
`mechanism if such a mechanism does not already exist in the
`LANs themselves.
`In accordance with another feature of the present inven(cid:173)
`tion, the quality of service management of a local area
`network is almost entirely concentrated in a single QoS
`
`Samsung Ex. 1006
`Page 12
`
`

`

`5,461,611
`
`4
`transmission path QoS allocation between a source station
`and a target station in the network of FIG. l;
`FIG. 10 shows a flow chart of the process of garbage
`collection in the quality of service path allocator of FIG. 1
`whereby only active allocations of bandwidth arc main(cid:173)
`tained in the allocator data base; and
`FIG. 11 shows a flow chart of the process of refreshing
`allocation requests in order to assure the continued alloca(cid:173)
`tion of the resources required to implement that allocation
`request.
`To facilitate reader understanding, identical reference
`numerals are used to designate elements common to the
`figures.
`
`DETAILED DESCRIPTION
`
`3
`management station on the LAN, thereby significantly
`reducing the complexity of introducing QoS management
`into existing LAN networks. The QoS management station
`includes the topology data base required for path allocation
`as well as mechanisms to support for allocation requests and 5
`responses.
`In accordance with yet another aspect of the present
`invention, QoS allocations are maintained only so long as a
`requestor continues to refresh the request. This fail safe
`garbage collection arrangement ensures rapid release of 10
`network facilities when a source or destination station of a
`multimedia transmission fails, or when a transmission path
`itself fails.
`In accordance with another feature of the present inven(cid:173)
`tion, network topology information and current data stream 15
`allocations are maintained in a hierarchical data base with a
`predetermined plurality of data objects and their associated
`attributes. This data storage arrangements minimizes the
`programming effort required to create and maintain the
`topology data base.
`In further accordance with the present invention, quality
`of service management of local area networks is carried out
`by means of messages exchanged between the multimedia
`source, the multimedia target ( destination) and the multime(cid:173)
`dia QoS path allocator. These messages include QoS allo(cid:173)
`cation requests, allocation confirmations, de-allocation
`requests, allocation change requests and allocation change
`confirmations.
`
`20
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`Referring more particularly to FIG. 1, there is shown a
`detailed block diagram of a quality of service management
`system for local area networks comprising a prior art local
`area network (LAN) 17 comprising a plurality of stations HI,
`29, ... , attached thereto. LAN 17 may, for example, be a
`Token Ring network. In accordance with the present inven(cid:173)
`tion, also attached to LAN 17 is a quality of service (QoS)
`allocator 20 which implements a quality of service manage-
`25 ment process for LAN 17.
`More particularly, station 10 is the source of a desired
`multimedia transmission and comprises an application n
`which requests a QoS connection to the destination or target
`30 station 29. Application 11 also is responsible for causing the
`transmission of the multimedia data stream, via the LAN
`transport protocol stack, 15 to the target station 29. Source
`station 10 also includes a QoS requestor manager 12 and a
`QoS protocol machine 13. Together, components 12 and 13
`assemble a request to reserve a QoS connection for a
`multi-media data stream on that path through the LAN 17
`between source station 10 and target station 29. Using a
`standard LAN transport protocol 15 to format a request
`packet, the packet is launched on LAN 17 through a medium
`40 access control (MAC) entity 16. LAN transport protocol 15
`and MAC 16 are standard parts of all stations attached to a
`LAN, the details of which are determined by the LAN itself,
`and will not be further described here except to note that
`standard MAC functions are defined in IEEE standards
`802.5 for token ring networks while LAN transport proto(cid:173)
`cols are provided by systems such as NET BIOS (IBM
`Manual SC30-3383) or TCP/IP (IBM Manual GG24-3376).
`Target station 29 similarly includes an application 26 which
`is capable of receiving and utilizing the multimedia data
`50 stream transmitted from application 11 in station. 10. The
`overall function of allocator 20 is to receive the QoS request
`from station 10, examine the resources of LAN 17, and
`determine if a path exists in LAN 17 between station 10 and
`station 29 which satisfies the requested level of QoS. If the
`QoS exists, it is assigned to this QoS data stream. If the QoS
`is not available, station 10 is notified of the lack of an
`adequate QoS path to the intended destination.
`It should be noted that application 11 may simply be a file
`server application which causes multimedia data to be
`transported from a multimedia data base to LAN 17. One
`such server application is the IBM OS/2 LAN Server
`program described in IBM Manual S04G-1046. The QoS
`requestor manager 12 interacts with application 11 using
`internal messages as is well known in the art and utilizes
`65 QoS protocol machine 13 to format the QoS request.
`QoS allocator 20 is a station attached to LAN 17 which
`manages the QoS requests for the entire LAN 17. Like other
`
`35
`
`A complete understanding of the present invention may be
`gained by considering the following detailed description in
`conjunction with the accompanying drawings, in which:
`FIG. 1 shows a general block diagram of the Quality of
`Service (QoS) management system of the present invention
`for managing LAN facilities so as to provide requested
`quality-of-service parameters for data streams flowing
`through the network;
`FIG. 2 shows a graphical representation of the hierarchi(cid:173)
`cal data base structure used to support the QoS management
`system of FIG. 1;
`FIG. 3 shows a typical graphical representation of a QoS
`message in the system of FIG. 1 and, in particular, an 45
`allocation request message sent from a source station in the
`LAN configuration of FIG. 1 to the QoS allocator station of
`FIG. 1;
`FIGS. 4 and 5, taken together, show a flow chart of the
`process of making a quality of service allocation for a
`multimedia transmission path between a source station and
`a target station in the network of FIG. 1;
`FIG. 6 shows a flow chart of the process of making a
`quality of service de-allocation of a multimedia transmission
`path previously established between a source station and a
`target station in the network of FIG. 1;
`FIG. 7 shows a flow chart of the process of increasing the
`bandwidth of a previously established multimedia transmis(cid:173)
`sion path QoS allocation between a source station and a 60
`target station in the network of FIG. 1;
`FIG. 8 shows a flow chart of the process of decreasing the
`bandwidth of a previously established multimedia transmis(cid:173)
`sion path QoS allocation between a source station and a
`target station in the network of FIG. 1;
`FIG. 9 shows a flow chart of the process of reducing the
`delay requirements of a previously established multimedia
`
`55
`
`Samsung Ex. 1006
`Page 13
`
`

`

`5,461,611
`
`5
`stations, allocator station 20 includes a Medium Access
`Control (MAC) entity 21 and a LAN transport protocol stack
`22 which provide the same functions for allocator station 20
`as the similar entities provide for stations 10 and 29.
`Allocator station 20 also includes a QoS requestor manager
`23 which, together with QoS protocol machine 24 receives,
`decodes and acts upon the QoS request from source station
`10. In carrying out its management functions, manager 23
`utilizes the data in QoS allocation data base 25 which, in
`general, contains all of the quality of service parameters for
`each of the components of LAN 17, as well as descriptions
`of all of the data streams already accepted by allocator 20
`and the detailed constituents of the connection paths for each
`of those data streams. Before proceeding to a description of
`the operation of the quality of service management system 15
`of FIG. 1, the detailed contents of the database 25 will be
`discussed.
`In FIG. 2 there is shown a graphical representation of the
`contents of the quality of service allocation management
`information database 25 of FIG. 1. As can be seen in FIG. 20
`2, the management information database is hierarchical
`having seven classes of information objects to created,
`edited and retrieved. In order to understand the data base
`information represented in FIG. 2, the following definitions
`are in order. Quality of service management, in the present 25
`context, means the satisfaction of a number of parameters
`describing the quality of service required on a transmission
`path through a local area network (such as LAN 17) in order
`to initiate the transmission of multimedia digital signals on
`that path. While quality-of-service parameters that describe
`the service expected from the network can be specified in
`many different ways, for the purposes of this application, the
`following parameters are used:
`Throughput-Forward Direction. The average throughput in
`bits per second over an interval of length T from source
`station 10 to target station 29.
`Throughput-Backward Direction. The average throughput
`in bits per second over an interval of length T from the
`target station 29 to the source station 10.
`End-to-End Delay-Forward Direction. The maximum 40
`elapsed time between the storage of a packet in the LAN
`entry device at source station 10 and the reception of the
`packet from the LAN exit device at target station 29.
`End-to-End Delay-Backward Direction. The maximum
`elapsed time between the storage of a packet in the LAN 45
`entry device at the target station 29 and the reception of
`the packet from the LAN exit device at source station 10.
`Delay Violation Ratio. The number of packets per hundred
`million which are not delivered within the End-to-End
`Delay, assumed to be identical in both directions.
`In addition, the multimedia data that is to be transmitted
`can be characterized by the following set of traffic descrip(cid:173)
`tors:
`Maximum Packet Size-Forward Direction. The maximum
`length of the data unit submitted to the LAN transport 55
`protocol stack 15 (e.g., the length of a Logical Link
`Control Protocol Data Unit (LPDU)) that is submitted to
`the MAC layer of the system for transmission from the
`source station 10 to the target station 29.
`Maximum Packet Size-Backward Direction. The maxi- 60
`mum length of the data unit submitted to the MAC layer
`of the system for transmission from the target station 29
`to the source station 10.
`Average Packet Size-Forward Direction. The average
`length of the data unit submitted to the network for 65
`transmission from the source station 10 to the target
`station 29.
`
`6
`Average Packet Size - Backward Direction. The average
`length of the data unit submitted to the network for
`transmission from the target station 29 to the source
`station 10.
`5 Committed Burst Size-Forward Direction. The maximum
`amount of data that the MAC layer of the LAN agrees to
`transfer over an interval of time T, from the source station
`10 to the target station 29, and may or may not be
`interrupted, where T==Committed Burst Size/Throughput.
`Committed Burst Size-Backward Direction. The maxi-
`mum amount of data that the MAC layer of the LAN
`agrees to transfer over the interval of time T, from the
`target station 29 to the source station 10, and may or may
`not be interrupted.
`Excess Burst Size-Forward Direction. The maximum
`amount of data in excess of Committed Burst Size that the
`MAC layer of the LAN will attempt to deliver over the
`interval of time T, from the source station 10 to the target
`station 29, and may or may not be interrupted.
`Excess Burst Size-Backward Direction. The maximum
`amount of data in excess of Committed Burst Size that the
`MAC layer of the LAN will attempt to deliver over the
`interval of time T, from the target station 29 to the source
`station 10, and may or may not be interrupted.
`Access Class-Forward Direction. The type of service to be
`provided by the LAN segment of source station 10, e.g.,
`access priority, synchronous, asynchronous, etc.
`Access Class-Backward Direction. The type of service to
`be provided by the LAN segment of target station 29.
`With these quality of service parameters and traffic
`30 descriptors in mind, the discussion of the database illustrated
`in FIG. 2 can be seen to include a plurality of data objects
`including an allocator data object, requestor object, segment
`object, bridge object, an end-to-end QoS stream object, a
`component stream object, and data objects for the various
`35 attachments to the LAN. More particularly, the allocation
`data base 25 of FIG. 1 contains the following object classes
`to be managed:
`Allocator 30---This class provides a summary view of the
`QoS Allocator's activity and has the following attributes:
`1. Network Address: The network address that identifies
`the Allocator.
`2. RefreshTimerDuration: The duration that the allocator
`waits for a refresh frame before incrementing the
`AgeSinceRefresh counter.
`3. AgeLimit: The threshold of the AgeSinceRefresh
`counter.
`4. InitializationTirne: The time-of-day value the system
`initialized for receiving Allocation requests.
`5. PresentThreshold: The time the Allocator 20 waits for
`a reply from a requestor station to an AllocatorPresen(cid:173)
`tAnnounce message.
`6. PresentRetryThreshold: The number of times the Allo(cid:173)
`catorPresentAnnounce message
`is
`re-sent
`to a
`requestor.
`QoS Requester 33-This class provides a summary view
`of a single Requester in the network and has the following
`attributes:
`1. Network Address: The network address that identifies
`this requester.
`2. StreamCount: A count of the number of data streams for
`which QoS is currently allocated by this requestor.
`3. InitializationTime: The time-of-day value when the
`system is initialized for receiving Allocation requests.
`Segment 32--Represents QoS related information for a
`single segment (e.g., Token Ring), having the following
`
`10
`
`50
`
`Samsung Ex. 1006
`Page 14
`
`

`

`7
`
`5,461,611
`
`10
`
`attributes:
`1. SegmentlD: An identifier of a particular LAN segment.
`This identifier should have the same format as the
`segment identifier in the Route Designator Fields.
`2. SegmentType: Identifies the type of segment (e.g., 4 mb 5
`Token Ring, 16 mb Token Ring, FDDI asynchronous.,
`etc.).
`3. PropagationDelay: The maximum delay that a bit
`experiences when crossing this segment. This attribute
`should be dynamically changeable.
`4. NumberOfAttachments: Current count of the number
`of attachments on the segment that are QoS reserved
`data stream sources to the segment.
`5. CurrentBandwidthAIIocated: The current aggregate
`bandwidth allocated to data streams on this segment. 15
`This attribute should be dynamically changeable.
`6. TrSegment: The aggregate current and minimum band(cid:173)
`widths allocated to QoS reserved data streams running
`at specific priorities on this segment.
`7. BridgesConnected: The network configuration of 20
`bridges directly connected to this segment. This
`attribute should be dynamically changeable.
`8. AttachmentList: The network configuration of attach(cid:173)
`ments such as LAN Adaptors that are connected to this
`segment, along with the MAC address of each.
`Bridge 31-Represents QoS related information for a
`single bridge and includes the following attributes:
`1. BridgelD: An identifier of a particular bridge. This
`identifier should have the same format as the bridge
`identifier in the Route Designator Fields.
`2. ProcessingDelay: The maximum delay that a packet
`experiences when passing through this bridge. This
`attribute should be dynamically changeable.
`3. MaxBandwidthAllocatable: The threshold aggregate 35
`bandwidth allocatable to QoS reserved data streams
`through this bridge. This attribute should be dynami(cid:173)
`cally changeable.
`4. BandwidthAllocated: The current aggregate bandwidth
`allocated to QoS reserved data streams running through 40
`this bridge.
`5. SegmentsConnected: The network configuration of
`segments connected to this bridge, including their
`SegmentID and their MaxBandwidthAllocatable.
`QoSStream 42-Represents a QoS reserved end-to-end
`data stream and has the following attributes:
`1. StreamID: An identifier, assigned by the allocator, that
`identifies this QoS reserved end-to-end data stream.
`2. Route Designator Fields: Identifies the segments and 50
`bridges that the data stream passes through end-to-end
`(the network components between the source and des(cid:173)
`tination MAC addresses). In the case where the source
`and destination stations are on the same segment (as in
`FIG. 1 ), this field identifies only the LAN segment.
`3. Traffic Descriptors: Parameters, as defined above, char(cid:173)
`acterizing the data stream presented to the network for
`transmission.
`4. QoSGranted: The QoS parameters that identified the
`QoS allocation granted by the QoS allocator. These are 60
`defined in the QoS parameter definitions above.
`5. SoureeMACAddress: The MAC address of the attach(cid:173)
`ment that is the source of the data stream.
`6. DestinationMACAddress: The MAC address of the 65
`attachment that is the destination of the data stream.
`7. AgcSineeRefresh: A counter indicating a period of time
`
`8
`since a refresh message has been received for an
`allocation of QoS for this data stream.
`8. AccessClass: Indicates the class under which the QoS
`reserved data stream accesses the EAN. For a complete
`description of this field, see the QoS definitions above.
`LANAttachment 35-Represents an adapter (e.g., Token
`Ring adaptor in a station) that is the source of QoS reserved
`data streams on a particular segment, and having the fol(cid:173)
`lowing attributes:
`1. MACAddress: The MAC address of this attachment.
`2. StreamCount: The count of the number of QoS reserved
`data streams passing through this attachment.
`BridgeAttachment 36-Represents an adapter (e.g.,
`Bridge attachment) that sources QoS reserved data streams,
`and having the following attributes:
`1. BridgelD: An identifier that identifies a bridge attach(cid:173)
`ment to a segment.
`2. StrearnCount: The count of the number of QoS reserved
`data streams passing through this attachment.
`Before proceedi