l|||||lllllllllllllllllllll|||||llllllllllllllllllllIllllllllllllllllllllll
`U8005355374A
`_
`5,355,374
`[11] Patent Number:
`[19]
`Unlted States Patent
`
`Hester et a1.
`[45] Date of Patent:
`Oct. 11, 1994
`
`[54] COMNIUNICATION NETWORK WITH
`DIVISIBLE AUXILLIARY CHANNEL
`ALLOCATION
`
`[75]
`
`Inventors: Phillip Hester, Indian Harbour
`Beach; wflfiam Highsmith; Don
`Mcmmel’bmh onndlalannc’ 3110f
`Fla.; Alan Lusk, Dallas, Tex.
`.
`_
`.
`Screntific-Atlanta, Inc., Atlanta, Ga.
`[73] Assrgnee:
`[21] Appl. No.: 165,830
`‘
`[22] Filed:
`
`Dec. 14, 1993
`
`Related US. Application Data
`Division of Ser. No. 880,209, May a, 1992, abandoned.
`
`[62]
`
`Int. Cl.5 ................................................ HMJ 3/22
`[51]
`[52] US. Cl. ..................................... 370/84; 370/95.1;
`455/54_2
`[58] Field of Search .................... 455/491, 53.1, 54.2,
`455/68; 379/58, 63; 370/69.l, 84, 95.1, 95.3;
`340/825.03, 825.07, 825.54
`
`[56]
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`4,477,809 10/1984 Bose ................................... 455/54.2
`
`.. 455/542
`4,553,262 11/1985 Coe ........
`
`.. 370/95.3
`4,763,325
`8/1988 Wolfe et al.
`4,780,715 10/1988 Kasagai ...............
`455/542
`4/1991 Modisette, Jr. et a1.
`............. 370/84
`5,005,171
`
`Primary Examiner—Benedict V. Safourek
`Attorney, Agent, 0,. Firm—Banner, Birch, McKie &
`Beckett
`ABSTRACT
`[57]
`A communication network havmg a master and a pm.
`rality of remotes, these remotes supporting a plurality of
`co-services,
`in which access to inbound frequencies
`among the 161119165 is Shared- When a Feed, by a ”mom
`for an extraordinary amount of bandw1dth is detected, a
`reserved spillover frequency from a set of frequencies is
`reserved for that remote. This bandwidth is reallocated
`when the need for extraordinary bandwidth for that
`remote has ended.
`
`9 Claims, 6 Drawing Sheets
`
`
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`1 1
`
`12
`
`
`13-15
`
`
` 2
`1
`III-III...-
`
`
`E%mm24‘4 1]il
`
`
`SUBCHANNELB
`
`—l-
`
`>_.|- Q—+
`
`.—
`A2 SITE3 —-
`ii
`A2 SITES
`Bt SITE2
`82 SITE4
`1 SITE2
`B2 SITE4
`— 82 SITE2
`32 SITE4
`_ B SITE4
`
` CONTENTION
`
`
`
`Petitioner Cisco Systems - Exhibit 1013 - Page 1
`
`Petitioner Cisco Systems - Exhibit 1013 - Page 1
`
`

`

`US. Patent
`
`Oct. 11, 1994
`
`Sheet 1 of 6
`
`5,355,374
`
`FIG. 1
`
`REMOTE?
`
`REMOTE1
`
`
` REMOTE4
`
`REMOTEZ
`
`
`
`Petitioner Cisco Systems - Exhibit 1013 - Page 2
`
`Petitioner Cisco Systems - Exhibit 1013 - Page 2
`
`

`

`US. Patent
`
`Oct. 11,
`
`1994
`
`Sheet 2 of 6
`
`5,355,374
`
`SK“vEOEmz
`
`Aomkzoo
`
`mesz
`
`Jomhzoo
`
`mmzbmfioo
`
`me>>._.m_z
`
`._OE.zOo
`
`405.200@meEmz
`
`mv
`
`wao/E
`
`Io.:>>w
`
`«.mzm
`
`om
`
`mmZmomE
`
`mesz
`
`Fzmgmo<z<2om
`
`xrmkozwm
`
`mgmfi.
`
`
`
`ZOF<>mmwmmmwmmlflmmhmz
`
`>oszOmE
`
`
`
`mmflmmT:.z>w
`
`x22I529E
`
`o_n_n.<E.
`
`mohomkwo
`
`mo_>mmw
`
`mo<mmmhz_
`
`Petitioner Cisco Systems - Exhibit 1013 - Page 3
`
`Petitioner Cisco Systems - Exhibit 1013 - Page 3
`
`
`
`
`
`
`
`
`

`

`US. Patent
`
`a
`
`S
`
`Ru
`
`.5.33.,
`
`4.7.3,
`
`
`
`0A"HHHHHHHHHHHHHHHHHHH"HHHHmeHbinmHHWflHQmummHHH
`
`
`
`
`
`kumdfiHUmmenduamuoEwmHamnhwfiomlawuofiwm
`
`
`
`
`
` UwHMH"MlunnmflmmmUmnunnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnvmAxnuuunxn»uuuuuuuuuuuuuuuuHmnmfimmnflumfluflnfixun.uAunx00£mmou
`
`AHHHHHHHHHUHmUHHMHHU
`
`
`
`
`
`
`
`
`
`Aunuununmmoflbhmmamummz
`
`MIIIGUflmmmUwhmIIIIIIvMA11111111
`
`
`HmnmflmEnwu:wAnuMoonnouhIII
`
`nuwmqmnoUmnmnnnnnnv
`
`
`
`A"H""HHHHHHHHHHHHHHWHHHHHHHHHmwvflprmgmflHQmumwflflfl
`
`mGE
`
`Petitioner Cisco Systems - Exhibit 1013 - Page 4
`
`Petitioner Cisco Systems - Exhibit 1013 - Page 4
`
`

`

`US. Patent
`
`Oct. 11, 1994
`
`Sheet 4 of 6
`
`5,355,374
`
`
`
`
`
`ulnmmao“munmnonsmuuuuuuuuuuuuuuuuuuuuuuuuuuuvAIIIIIIIIIIIIIIIIII
`
`
`llllllllllllllllHmnmfimEku:
`
`uuHoomGemmmdu
`
`A m
`
`
`
`xwUfihuwfin
`
`AunnnanQSmmmSu
`
`
`
`AnnunuflwbwEkun
`
`H0
`
`Hmummz
`
`Hmuofimm
`
`
`
`Annunwbmm.ufinan
`
`HmnmflmmnHMMfiuflnwnnuIIIGOAUflGHumUcanonnmnnnnnnnnnnnnnnnnnnnnnnnnnnvAuuuuuuuuuuuuuuuuuuuuuuuuuuu
`
`
`
`
`
`
`
`
`
`AnnoyInloflnuwfinOHumnflfihmunnnnnnnnnnnnnnnnnnnnnnnnnnv
`
`
`
`
`
`m.GE
`
`Petitioner Cisco Systems - Exhibit 1013 - Page 5
`
`Petitioner Cisco Systems - Exhibit 1013 - Page 5
`
`

`

`US. Patent
`
`Oct. 11, 1994
`
`Sheet 5 of 6
`
`5,355,374
`
`zo_._.zm._.zoo
`
` 9.?NF:
`m4mzz<IOmDm<._mzz<Iom3w
`Ill-Ill...
`o—mmnomvmNFm?
`
`m.GE
`
`Petitioner Cisco Systems - Exhibit 1013 - Page 6
`
`Petitioner Cisco Systems - Exhibit 1013 - Page 6
`
`
`
`

`

`US. Patent
`
`l,
`
`eIn
`
`.3
`
`aw73,
`
`
`
`nnunfiHm3onunu
`
`
`
`
`
`UOEmn“wandsHmuofiwm
`
`
`
`IIHQuooHHmummoumonnuwuuuuuuuuuuuuuuv
`
`
`
`
`
`
`
`
`
`
`
`SAnnnnnnnumwsvmamoaum>nmmwhuuuuuuuuuuuuuuuu
`
`nunmeHHHoouuv...
`
`
`
`
`
`fiuuuuuuuuuu.QuUOHHm.0.Qnnnnnnnnnnnnnnnnnnnnnnv5HMGmflm"GUMHQHHOUHH
`
`
`Honnmnonsm.99.............vESMMQUHa[$9.555qu OOHHMIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIvMAuuuuuuuuuuuuuuuuuuwumumsooHHm[lampummsvwhrulnMAHHHHfimm
`
`
`
`
`
`
`
`
`
`wumumsUOHHMlnuanuooaamnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnvwAuuuuuuuuuuuuuuuuuu
`
`
`
`
`
`umwduwnuilx.OAnunfiuunfiMw3omn
`
`umoSanxxxx”AHHHHHHHHHuwwmwh—u"1nuo
`4AuuuuuuuuuuuuuuuuuuwumwnsooHHm
`
`
`
`
`nuanuUOHHmuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuv
`
`k.GE
`
`Petitioner Cisco Systems - Exhibit 1013 - Page 7
`
`Petitioner Cisco Systems - Exhibit 1013 - Page 7
`
`

`

`1
`
`5,355,374
`
`2
`bandwidth, by using an auxiliary, “spillover” channel to
`which a remote can be temporarily assigned.
`Another embodiment of the present invention pro-
`vides a communication network having a master and a
`plurality of remotes, these remotes supporting a plural-
`ity of co-services, the network comprising means for
`sharing access to at least one slotted frequency among
`the remotes, means for detecting a need by a remote for
`an extraordinary amount of bandwidth, means for allo-
`cating to at least one remote a reserved set of slots of a
`frequency in response to the detection of a need for
`extraordinary bandwidth for that remote, and means for
`reallocating the slots which the at least one remote has
`been allocated so as to make said allocated slots avail-
`able for use by all remotes in the network when the
`need for extraordinary bandwidth for that remote has
`ended, and means for determining the end of the need
`for extraordinary bandwidth by a credit mechanism.
`This embodiment of the present invention provides
`an efficient mechanism for determining the utilization of
`allocated bandwidth by a remote, and causes the remote
`to return the allocated bandwidth to the network when
`the utilization falls below (or exceeds) a predetermina-
`ble threshold.
`Another embodiment of the present invention pro-
`vides a communication network having a master and a
`plurality of remotes, these remotes supporting a plural-
`ity of co-services, the network comprising means for
`sharing access to at least one slotted frequency among
`the remotes, means for detecting a need by a remote for
`an extraordinary amount of bandwidth, said remote
`being a demanding remote, means for allocating to a
`demanding remote at least one reserved set of slots
`corresponding to at least one initial subchannel of a
`frequency in response to the detection of a need for
`extraordinary bandwidth for that remote, means for
`dividing the initial subchannel into separate secondary
`subchannels and assigning different secondary subchan-
`nels to a plurality of different demanding remotes,
`means for
`recombining the secondary subchannels
`which have been divided when the need for extraordi-
`nary bandwidth for one of the demanding remotes using
`one of the divided secondary subchannels has ended.
`This embodiment of the present invention prevents
`the blocking of remotes which may otherwise occur if
`fewer channels are defined than are actually needed. It
`also avoids the problem of a single site using only l/n of
`the available bandwidth (noneffective use of the allocat-
`able bandwidth) that otherwise occurs if the bandwidth
`of the subchannels is fixed and “n” is the number of
`available subchannels.
`Another embodiment of the present invention pro-
`vides a communication network having a master and a
`plurality of remotes, these remotes supporting a plural-
`ity of co-services, the network comprising means for
`sharing access to inbound frequencies among the
`remotes, means for detecting a need by a remote for an
`extraordinary amount of bandwidth, means for allocat-
`ing to a remote a reserved amount of bandwidth in
`response to the detection of a need for extraordinary
`bandwidth for that remote, and means for informing
`each of the remotes of the network of the allocations of
`the bandwidth.
`This embodiment of the present invention provides
`for efficient use of the dynamically allocated bandwidth
`by requiring that the community of sites be aware of
`and abide by the allocations. This occurs even where
`the remote site has experienced a temporary inability to
`
`COMMUNICATION NETWORK WITH DIVISIBLE
`AUXILLIARY CHANNEL ALLOCATION
`
`This application is a division of application Ser. No.
`880,209, filed May 8, 1992, now abandoned.
`FIELD OF THE INVENTION
`
`The present invention relates to the field of communi-
`cation networks having a master and a plurality of
`remotes, and more specifically to the allocation of ex-
`traordinary bandwidth on demand to a remote or
`remotes.
`
`BACKGROUND OF THE INVENTION
`
`A communication network may comprise, for exam-
`ple, a number of remote satellite communication termi-
`nals (or “remotes”) that communicate either with a hub
`(terminal or “master”) or with one of the other remotes
`through the master. The outbound frequencies from the
`master are broadcast, while the inbound frequencies are
`shared using any of a variety of access methods. Some
`of these access methods include: TDMA, contention
`(slotted aloha), demand-assigned and others.
`Each of the remotes can provide access to the net-
`work for a number of co-services through the remote’s
`RF equipment. Some of these co-services include: Data
`(interactive, LANs, computer-computer, etc.); digital
`voice (switched, unswitched); SCADA (unswitched);
`digital video (switched, unswitched); and others. A
`problem with such an arrangement is due to the require-
`ment of supporting different types of co-services. Some
`of these co-services are characterized as “bursty” traf-
`fic, and include LANs, file transfers, demand voice and
`others. This bursty traffic significantly exceeds the av-
`erage bandwidth requirement for the community of
`remotes that share the inbound and/or the outbound
`frequencies. Interactive response time could suffer, or
`one type of service might dominate others with respect
`to traffic engineering.
`There is thus a need for a network in which remotes
`are allocated bandwidth on demand in an efficient man-
`ner, and in which this bandwidth is reallocated among
`the remotes when it is nojonger demanded by a specific
`remote or remotes. There is also a need for a network in
`which the community of sites reliably are made aware
`of and abide by the allocations.
`SUMMARY OF THE INVENTION
`
`These and other needs are met by the present inven-
`tion which provides a network and a method for operat-
`ing a communication network having a master and a
`plurality of remotes, these remotes supporting a plural-
`ity of co-services. The network comprises means for
`sharing access to inbound frequencies among the
`remotes, means for detecting a need by a remote for an
`extraordinary amount of bandwidth, and means for
`allocating to a remote 'a reserved spillover frequency
`from a set of frequencies in response to the detection of
`a need for extraordinary bandwidth for that remote.
`There are also means for reallocating the remote which
`has been allocated to the spillover frequency to one of
`the remaining frequencies when the need for extraordi-
`nary bandwidth for that remote has ended.
`With the present invention, a network is provided
`that responds to needs for extraordinary amounts of
`bandwidth, without wasting an excessive amount of
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Petitioner Cisco Systems - Exhibit 1013 - Page 8
`
`Petitioner Cisco Systems - Exhibit 1013 - Page 8
`
`

`

`5,355,374
`
`3
`hear the broadcasted allocations due to a rain fade or
`electrical interference, for example, or when a new
`remote site has been installed in the network.
`Other objects, advantages and novel features of the
`present invention will become apparent from the fol-
`lowing detailed description of the invention when con-
`sidered in conjunction with the accompanying draw-
`ings.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`4
`mote is assigned to one of the spillover frequencies for
`the duration of a demand period.
`A single, exemplary remote 1 and a master 10 are
`shown in more detail in block diagram form in FIG. 2.
`The remote 1 has a plurality of service interfaces 20, 22
`that provide an interface between the co-service and the
`remote 1. The co-service coupled to service interface 20
`may be data, for example, while the co-service coupled
`to service interface 22 may be a LAN.
`The service interfaces 20, 22 are each coupled to a
`packet multiplexer 24 which multiplexes the different
`co-services together and provides them to a transmitter
`26 for transmission. A frequency synthesizer 28 controls
`the frequency the transmitter 26 and a receiver 30 are
`on. The frequency synthesizer 28 is controlled by sig-
`nals from network management 32, which is also cou-
`pled to receive information from the packet multiplexer
`24 and a traffic detector 34. The remote 1 has a reserva-
`tion table 36 that keeps track of what frequencies are
`0 being used in the network.
`The master 10 comprises a network control computer
`40 that controls a number of modems and demods, with
`a separate modem and demod assigned to each fre-
`quency. Data is routed through a packet switch 42. The
`network control computer 40 of the master 10 has a
`frequency pool table 44 that keeps track of the frequen-
`cies being used and the availability of the remainder.
`The computer 40 also has an access manager coupled to
`an access plan and a network definition.
`The traffic detector 34 of the remote I detects condi-
`tions or events that indicate the need for an extraordi-
`nary amount of bandwidth for a co—service. Some of
`these are automatic, application-related events, such as
`a telephone going off—hook; network congestion; excess
`queuing or aging of data; perceived burst of traffic;
`circuit setup request. Others are administrative proce-
`dures such as manual operator intervention and timed
`events. Other events or conditions may also indicate the
`need for more bandwidth.
`In addition to detecting the events or conditions that
`trigger the need for more bandwidth, the traffic detec-
`tor also detects when this bandwidth is no longer
`needed. These signals may include, but are not limited
`to: a telephone going on-hook, cessation of network
`congestion, depletion of an awaiting queue, end of a
`perceived burst of traffic, circuit clear request, manual
`operator intervention, and timed events.
`The traffic detector 34 detects the conditions or
`events requiring the use of a spillover frequency in a
`conventional manner. For example, the traffic detector
`34 monitors the status messages from voice codec units
`and can determine when the telephone goes on or off
`hook. Going off-hook causes the traffic detector 34 to
`send a signal to the network management 32 to request
`the use of a spillover frequency. After the call is com-
`pleted, the telephone goes on hook and this is detected
`by the detector 34. Another signal is sent from the de-
`tector 34 to the network management 32 to inform it
`that there is no longer a need for the extraordinary
`bandwidth. The telephone on-hook/off-hook example
`described above is but one example of detectable condi-
`tions or events that are used by the network manage-
`ment 32 to determine the need for extraordinary band-
`width.
`One exemplary procedure followed by the network
`management 32 and the master station 10 is illustrated in
`FIG. 3 using the example of off-hook/on—hook as deter-
`mining the need for extraordinary bandwidth. In step a),
`
`10
`
`15
`
`FIG. 1 is a block diagram of a communication net-
`work constructed in accordance with an embodiment of
`the present invention.
`FIG. 2 is a block diagram illustrating in more detail a
`single remote and a master from the network of FIG. 1.
`FIG. 3 illustrates an exemplary protocol for manag-
`ing the spillover frequencies in accordance with an
`embodiment of the present invention.
`FIG. 4 illustrates a superframe divided into N slots 2
`per frame.
`FIG. 5 illustrate an exemplary process according to
`an embodiment of the present invention for terminating
`an allocation, and for subdividing an allocated channel.
`FIG. 6 shows graphically an example of a process of
`subdividing a channel in accordance with an embodi-
`ment of the present invention.
`FIG. 7 illustrates a process in accordance with an
`embodiment of the present invention for providing
`reservation integrity.
`DETAILED DESCRIPTION OF THE
`DRAWINGS
`
`25
`
`30
`
`FIG. 1 illustrates an example of a communications
`network which uses the present invention. This net-
`work may comprise, for example, a number of remote
`satellite communication terminals (remotes 1—4) that
`communicate either with a hub (terminal or “master” 10
`) or with one of the other remotes through the master
`10. The outbound frequencies from the master 10 to the
`remotes are broadcast, while the inbound frequencies
`from the remotes to the hub are shared using any of a
`variety of access methods. Some of these access meth-
`ods include: TDMA, contention (slotted aloha), de-
`mand-assigned and others.
`Each of the remotes 1—4 can provide access to the
`network for a number of co-services through the re-
`mote’s RF equipment. Some of these include: Data (
`interactive, LANs, computer-computer, etc); digital
`voice (switched, unswitched); SCADA (unswitched);
`digital video (switched, unswitched); and others. A
`problem with such an arrangement as shown in FIG. 1
`is due to the requirement of supporting different types
`of co-services. Some of these co-services are character-
`ized as “bursty” traffic, and include LANs, file trans-
`fers, demand voice and others. This bursty traffic signif-
`icantly exceeds the average bandwidth requirement for
`the community of remotes 1—4 that share the inbound
`and/or the outbound frequencies. Interactive response
`time could suffer, or one type of service might dominate
`others with respect to traffic engineering.
`To solve this problem, the present invention provides
`two different sets of the inbound and outbound frequen-
`cies. These subsets are the “home frequencies” and the
`“spillover frequencies”. Normally, traffic is carried to
`and from the remotes over the home frequencies. When
`there is an indicated need for an extraordinary amount
`of bandwidth for a co-service, then that particular re—
`
`35
`
`45
`
`50
`
`55
`
`65
`
`Petitioner Cisco Systems - Exhibit 1013 - Page 9
`
`Petitioner Cisco Systems - Exhibit 1013 - Page 9
`
`

`

`5
`the remote 1 establishes services over home frequency 1
`(HomeFreql) with the master 10. At some point in time,
`the traffic detector 34 detects a telephone connected to
`remote I going off—hook. Accordingly, the traffic detec—
`tor 34 sends a signal to the network management 32 of
`remote I. The network management 32 then causes an
`initiating signal to be sent through the packet multi-
`plexer 24 to the master 10, (step b). The master 10 as-
`signs the remote 1 to a spillover frequency (AuxFreql
`in FIG. 3) in step c). The remote I then changes its
`frequency synthesizer 28 accordingly in step d), and
`services are established in step e).
`At some point in time, the telephone goes on-hook at
`remote 1, ending the need for the use of the spillover
`frequency. Remote 1 sends a termination signal to the
`master 10 in step 0, which then assigns the remote I to
`another home frequency HomeFreql in step g) . The
`remote 1 changes frequency in step h) .
`Other protocols than that illustrated in FIG. 3 for
`managing the spillover frequencies are contemplated
`and readily apparent to one of ordinary skill in the art.
`In an embodiment of the present invention, a remote
`will move all of its co-services together to the spillover
`frequency in addition to the co-service which caused
`the remote to request the use of a. spillover frequency.
`Also, more than one remote can share (simultaneously
`use) the spillover frequencies.
`In certain embodiments the spillover frequencies
`have a different timing structure than the home frequen-
`cies, while still supporting all co-services. For instance,
`a spillover frequency may have a predominance of
`voice slots, while the home frequency may have a pre-
`dominance of slots sized for interactive data traffic, and
`possibly no voice slots.
`In addition to the reserving of specific frequencies as
`spillover frequencies for on demand extra bandwidth,
`the present invention also relates to the use of a single
`frequency for inbound and outbound data. The fre-
`quency is divided into subchannels that are available on
`a contention basis, as described in commonly assigned
`US. Pat. No. 5,003,534. In that arrangement, certain
`subchannels are allocatable for use upon the satisfying
`of specific conditions, and are no longer subject to the
`contention process. The present
`invention improves
`upon this arrangement by providing a mechanism
`whereby the remote site can determine when it no
`longer needs the subchannel that has been allocated.
`FIG. 4 illustrates a “superframe” which contains a
`number of frames, with each frame having a number
`“n” of slots. The inbound frequencies are shared and
`slotted into “slotted frequencies” using any of a variety
`of access methods. Similarly to the spillover frequency
`embodiment, certain events or conditions indicate the
`need for an extraordinary amount of bandwidth for a
`period of time. This includes, but is not limited to: net—
`work congestion, excess queuing or aging of data, per-
`ceived burst of traffic, circuit setup request, manual
`operator intervention, or timed events. When one or
`more of these occur, the network responds by reserving
`a portion of the bandwidth (i.e. a number of slots) for
`the demanding remote site. Although the beginning of
`the demand period is normally clearly defined, the end
`of the demand period may be less distinct because of
`intermittent traffic from other terminals or short-term
`pauses in the application that triggered the demand
`period. It is because of this that the present invention
`provides a “credit mechanism” as described below.
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`5,355,374
`
`6
`The remote is allocated a portion of the bandwidth by
`being assigned a number of slots, for example three slots
`per frame. 50 that these slots are not wasted, once the
`demand for the extra bandwidth is over, the utilization
`of the allocated slots is monitored by the remote. If the
`remote is not utilizing the allocated slots to a given
`extent, then the remote will return the allocated slots
`back for reassignment. The utilization of the allocated
`slots is determined using a “credit mechanism”.
`The term “credit” is used here to mean the number of
`slots that a site may waste. A slot is wasted if it is exclu-
`sively assigned to a site and that site fails to use it. The
`remote, upon being allocated the slots, is given an initial
`credit, so that it may have some leeway to start using
`the slots. An “npcoun ” increases a remote’s credit each
`time the remote uses a slot. A “downcount” decreases a
`remote’s credit each time the remote fails to use a re-
`served slot. When the remote’s credit falls to or below
`zero, the remote must send a terminating signal so that
`the slots can be reallocated.
`An implicit priority scheme is provided by amount of
`initial credit that is to be given a remote, and the ratio of
`the amount of credit given for an upcount and that
`taken away by a downcount. For example, if a certain
`remote is to have a relatively high priority, then a large
`initial credit may be given to it, and more credit given to
`it for an upcount than is taken away by a downcount.
`This would obviously cause this remote a better oppor-
`tunity to remain using the reserved slots longer than a
`remote which has a higher value for a downcount than
`for an upcount.
`The operation of the credit mechanism should be
`readily apparent. Upon being granted reserved slots, a
`remote receives an initial credit, for example 15 credits.
`For each slot that it uses in the successive frames fol-
`lowing the granting of the slots, the remote may re-
`ceive, for example, 3 credits for each slot that it uses,
`and loses 2 credits for each slot that it fails to use. In this
`example, the remote will send a terminating signal after
`eight slots if it fails to use any of the slots, since it will
`have less than zero slots. If it does use the slots, how-
`ever, the remote will keep using the slots until such time
`as its credit reaches or falls below zero. There is a limit
`to how long a remote may occupy the reserved slots,
`and this is the “credit limi ” the maximum number of
`slots that a site may be credited. The credit limit obvi-
`ates the problem of a single remote accumulating a huge
`number of credits and then tying up the reservation
`slots for an excessive amount of time.
`Although described with respect to inbound band-
`width units, the above method can also be applied to
`other arrangements of bandwidth units, including out-
`bound time-division units. Also, the credit mechanism
`above can be used to “pre-qualify” a remote site for a
`subchannel (the reserved slots) allocation. In such a
`case, the remote site would measure for a period of time
`whether
`it “needs” an allocation.
`In the above-
`described embodiments of the present invention, the
`network management 32 performs the credit counting,
`etc.
`
`The process for establishing the reserved subchannel
`(slots) is illustrated in FIG. 5. The remote 1 will send an
`initiating signal after it has detected an initiating event.
`The master 10 will send back a subchannel definition
`and may also send back a termination metric. The re-
`mote 1 will then use the designated subchannel. After a
`termination event, or the credit reaches or falls below
`zero, the remote 1 sends the master 10 a termination
`
`Petitioner Cisco Systems - Exhibit 1013 - Page 10
`
`Petitioner Cisco Systems - Exhibit 1013 - Page 10
`
`

`

`7
`signal. The master 10 sends a subchannel definition
`clear signal. The remote I then uses the general pool of
`subchannels that are available.
`Instead of dividing the pool of allocatable slots into a
`set of determined, fixed subchannels, another embodi-
`ment of the present invention acts to subdivide chan-
`nels. This prevents some remotes from being blocked
`from reserved allocation if fewer subchannels are de-
`fined than are actually needed. It also obviates the prob-
`lem of a fixed bandwidth for the subchannels. Other-
`wise, if only one site is busy, it may only use l/n of the
`available bandwidth, where ‘n’ is the number of avail-
`able subchannels.
`To overcome this limitation, the allocatable slots as
`described above are pre-arranged into ‘n’ initial sub-
`channels, where n is any integer from 1 to ‘m’ and ‘m’ is
`the number of allocatable slots. The subchannels are
`allocated according to the methods described above.
`An example of the dividing of the channels into sub-
`channels according to the method of the present inven-
`tion is shown in FIG. 6. Before reviewing this example,
`the rules followed in this method are set forth below.
`If a request for an allocation arrives at the master
`station from remote “S” and no subchannels are avail-
`able, then the largest allocated subchannel “A” (allo-
`cated to site “F”) will be divided into two subchannels,
`“A1” and “A2”. Remote “F” will retain subchannel A1
`and remote “S” will be allocated subchannel A2.
`If remote F or remote S requests the deallocation of
`A1 or A2, then Al and A2 will be re-combined into
`subchannel A. Subchannel A will be re-allocated to the
`remaining remote F or S. However, the initial subchan-
`nels will not be combined. In effect, the “initial” sub-
`channels are considered a minimum number of available
`subchannels.
`An embodiment of the method of the present inven-
`tion prevents fragmentation of the subchannels by only
`re-combining subchannels with its “sibling”. In other
`words, if subchannel A is divided into A1 and A2, A1
`and A2 may only be re-combined back into A. A1 may
`not be re-combined with B2, for example. Other such
`procedures may be used for preventing fragmentation
`without departing from the scope of the invention.
`Another embodiment of the invention imposes a max-
`imum number of divisions in order to guarantee a mini-
`mum bandwidth of a subchannel. Still other dividing
`rule refinements can be followed without departing
`from the scope of the invention.
`As seen in FIG. 6, there are 15 slots in a given frame,
`as an example. Slots 1-6 are Subchannel A and slots
`7—12 are Subchannel B, with all of the slots in these
`subchannels being available for use on a contention
`basis when they are not reserved. Slots 13-15 remain
`available on a contention basis even when Subchannels
`A and B are reserved.
`In the illustrated example, all of the slots are available
`at first on a contention basis. Remote 1 then experiences
`an event or condition which requires the allocation of
`reserved bandwidth to it, so it is granted slots 1—6, sub~
`channel A. At some point in time thereafter, while re—
`mote 1 still requires extra bandwidth, remote 2 requires
`reserved bandwidth and is then allocated subchannel B.
`When remote 3 thereafter requires reserved bandwidth,
`there are no more slots left in the frame that can be
`reserved. In accordance with the dividing rules of the
`method of the present invention, subchannel A is di-
`vided in half so that remote 1 uses slots 1—3 and remote
`3 uses slots 4—6 on a reserved basis.
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`60
`
`65
`
`5,355,374
`
`8
`When remote 4 needs reserved slots, subchannel B is
`divided, as shown. Thereafter, remote 3 signals that it
`no longer needs the reserved slots. The divided sub-
`channel A now recombines so that only remote I is
`using the reserved slots of subcharmel A. Should remote
`I now also terminate its demand for reserved slots, then
`the slots of subchannel A become available for use on a
`contention basis, while subchannel B remains divided
`between remotes 2 and 4.
`The procedure for the establishment of a divisible
`subchannel according to the present invention is the
`same as that shown in FIG. 5.
`The present invention also provides allocation integ-
`rity, which requires that the community of remotes
`sharing the bandwidth be aware of and abide by the
`allocations. This may be complicated due to a remote
`having a temporary inability to hear broadcasted alloca-
`tion because of interference, rain fade, etc.. It is also
`caused by the new installation of a remote into the
`network.
`To overcome these problems, the present invention
`provides that a remote will signal the master 10 each
`time that it experiences a power interruption or machine
`reset. The master 10 then re—transmits all allocations to
`the remote, either by broadcasting or selectively ad—
`dressing the _remote. The master 10 may periodically
`broadcast a checksum or similar signal that represents
`the current allocations. Each site will use this signal to
`validate its stored record of current allocations. Any
`site that fails its validation will signal the master 10 to
`re-broadcast the current allocation. In another embodi-
`ment, the master 10 periodically re-broadcasts the com-
`plete current allocations (rather than a validation signal
`such as a table checksum).
`The master 10 directly monitors abidance of alloca-
`tions, and maintains a record of all allocations in a reser-
`vation table. The demodulator of the master 1!] that is
`associated with the shared frequency is able to signal
`the occurrence of a collision on a slot. By correlating
`the collision signal with the reservation table, the mas-
`ter 10 is able to determine that at least one site is “disre-
`specting" an allocation. When this occurs, the master 10
`will re-broadcast all allocations. It is also possible, as
`provided in another embodiment of the invention, to
`instead determine the specific allocations that are being
`violated and re-broadcast only those specific alloca-
`tions.
`
`Various functional arrangements are available for
`carrying out the above procedures. These functions
`include: detection of collisions, storage of reservation
`table, correlation of reservation table with collisions,
`and re-broadcast of allocations. These different func-
`tions can be provided in different locations according to
`different embodiments of the present invention. For
`example one or more of the functions will be located in
`the master's demodulation equipment that is associated
`with the shared frequency, while the remaining func-
`tions are located in the master station’s control com—
`puter 40.
`An illustrated example of the allocation integrity of
`the present invention is illustrated in FIG. 7. When the
`master is initially powered up, the master 10 then broad-
`casts an allocation table. After some time, remote 1 may
`have its power interrupted, so that it then sends a re