Title: Bandwidth management of virtual networks on a shared network
Abstract: An apparatus and method for equitably allocating bandwidth to virtual networks operating on a common physical network, such as a power-line network for homeowners sharing a single power-line distribution transformer. An ad-hoc master is selected from the virtual power-line network controllers. The master allocates bandwidth to streams based on their priority group categorization. By way of example, four priority groups (A-D) are described into which stream priority is classified, with the highest priority group for communicating isochronous streams, the lowest priority for transferring asynchronous streams and the other priority groups for communicating streams having an intermediate level of transmission priority. Within a given priority group all bandwidth requests are fulfilled for virtual networks requesting up to their fair share of the bandwidth within the priority group, and bandwidth available from virtual networks not utilizing their full share is allocated equally amongst those requesting more bandwidth.
Patent Number: 6,947,409 Issued on 09/20/2005 to Iwamura
| Inventors:
|
Iwamura; Ryuichi (San Diego, CA)
|
| Assignee:
|
Sony Corporation (Tokyo, JP);
Sony Electronics Inc. (Park Ridge, NJ)
|
| Appl. No.:
|
651519 |
| Filed:
|
August 29, 2003 |
| Current U.S. Class: |
370/345; 370/442 |
| Intern'l Class: |
H04J 003/00; H04B 007/21.2 |
| Field of Search: |
370/280,345-347,442-445,252,389,392,395.1,395.4,395.41,395.42,395.43
|
References Cited [Referenced By]
U.S. Patent Documents
| 3944723 | Mar., 1976 | Fong.
| |
| 4796027 | Jan., 1989 | Smith-Vaniz.
| |
| 5285443 | Feb., 1994 | Patsiokas et al.
| |
| 5392223 | Feb., 1995 | Caci.
| |
| 5623495 | Apr., 1997 | Eng et al.
| |
| 5630204 | May., 1997 | Hylton et al.
| |
| 5751712 | May., 1998 | Farwell et al.
| |
| 5953338 | Sep., 1999 | Ma et al.
| |
| 6026086 | Feb., 2000 | Lancelot et al.
| |
| 6125448 | Sep., 2000 | Schwan et al.
| |
| 6243818 | Jun., 2001 | Schwan et al.
| |
| 6278357 | Aug., 2001 | Croushore et al.
| |
| 6324184 | Nov., 2001 | Hou et al.
| |
| 6492897 | Dec., 2002 | Mowery, Jr.
| |
| 6718552 | Apr., 2004 | Goode.
| |
| 2002/0021701 | Feb., 2002 | Lavian et al.
| |
| 2002/0133589 | Sep., 2002 | Gubbi et al.
| |
| 2002/0178263 | Nov., 2002 | Hreha et al.
| |
| 2003/0005130 | Jan., 2003 | Cheng.
| |
| 2003/0037283 | Feb., 2003 | Srinivasan et al.
| |
| 2003/0043741 | Mar., 2003 | Mukai et al.
| |
| 2003/0088706 | May., 2003 | Chan et al.
| |
| 2003/0169728 | Sep., 2003 | Choi.
| |
| 2004/0062229 | Apr., 2004 | Ayyagari et al.
| |
| 2004/0143663 | Jul., 2004 | Leedom et al.
| |
| 2004/0160990 | Aug., 2004 | Logvinov et al.
| |
| 2004/0165528 | Aug., 2004 | Li et al.
| |
Primary Examiner: Kizou; Hassan
Assistant Examiner: Cho; Hong Soi
Attorney, Agent or Firm: O'Banion; John P.
Parent Case Text
CROSS-REFERENCE TO RELATED APPLICATIONS
This application claims priority from U.S. provisional application Ser. No.
60/456,024 filed on Mar. 17, 2003, incorporated herein by reference.
Claims
1. An apparatus for managing bandwidth allocated to a plurality of virtual networks
on the same shared network, comprising:
a server device configured for connection to a virtual network on a shared network
and configured to communicate with at least one other said server device; and
means associated with said server device for dynamically allocating bandwidth
to each virtual network on said shared network to which said server devices are
connected, and for reallocating said bandwidth if sufficient bandwidth on said
shared network is not available to simultaneously support bandwidth requirements
of said virtual networks;
wherein at any given time a said one of said server devices functions as an active
master server;
wherein said active master server functions to reallocate said bandwidth if sufficient
bandwidth on said shared network is not available to simultaneously support bandwidth
requirements of said virtual networks;
wherein said server device is configured to detect the presence of an active
master server when newly connected to a virtual network on said shared network
and, if no active master server is detected, to become said active master server;
and
wherein, upon disconnection of said active master server, another said server
device becomes said active master server.
2. An apparatus as recited in claim 1, wherein said shared network comprises
a physical power-line communication network.
3. An apparatus as recited in claim 1, wherein said means for dynamically allocating
bandwidth is configured to allocate the available bandwidth across a set of priority
groups into which data streams are categorized on the basis of data stream content.
4. An apparatus as recited in claim 3, further comprising means for establishing
a minimum amount of bandwidth to be allocated to each priority group.
5. An apparatus as recited in claim 3, wherein data streams having an isochronous
nature are categorized into a high priority group, while data streams having an
asynchronous nature are categorized into a lower priority group.
6. An apparatus as recited in claim 5, wherein said means for dynamically allocating
bandwidth is configured to categorize isochronous streams into group A or B, and
asynchronous streams into group C or D.
7. An apparatus as recited in claim 6, wherein VoIP (voice over internet protocol)
and audio or video streams for live-recordings are categorized in group A, playback
of audio/video streams is categorized in group B, web accesses are categorized
in group C, and file transfers are categorized in group D.
8. An apparatus as recited in claim 3, wherein said means for dynamically allocating
bandwidth is configured to fulfill all bandwidth requests of any virtual network
requesting up to its equal share of bandwidth within a given priority group, and
to equally share remaining bandwidth amongst virtual networks requesting more bandwidth
within a given priority group.
9. An apparatus as recited in claim 1, wherein said means for dynamically allocating
bandwidth is integrated within a device selected from the group of audio end video
devices consisting essentially of set-top boxes, computer servers, television sets,
audio and/or video recording devices, and audio and/or video playback devices.
10. An apparatus as recited in claim 1, wherein said means for dynamically allocating
bandwidth comprises:
a computer processor within said server device; and
programming executable by said computer processor for carrying out the operations
of
dividing the available bandwidth of the shared network into assignable units,
ordering streams, being transmitted over the shared network, into priority groups,
assigning units of bandwidth to said priority groups in response to the bandwidth
requirements of said streams and the transmission priority of said priority group,
and
assigning specific units of bandwidth to specific streams within each of said
priority groups in response to an equitable sharing of bandwidth between said virtual
networks sharing said shared network.
11. An apparatus for managing bandwidth allocated to virtual networks sharing
the bandwidth of a shared network, comprising:
a computer processor within a server device configured for communicating over
said shared network with other said server devices; and
programming executable on said computer processor for carrying out the operations
of
dividing the available bandwidth of the shared network into assignable units,
categorizing streams for transmission over said shared network into priority
groups,
assigning sections of bandwidth to said priority groups in response to the bandwidth
requirements of said streams and the transmission priority of said priority group,
and
assigning units of bandwidth to specific streams within each of said priority
groups;
wherein at any given time a said one of said devices functions as an active master
server;
wherein said active master server functions to reallocate said bandwidth if sufficient
bandwidth on said shared network is not available to simultaneously support bandwidth
requirements of said virtual networks;
wherein said server device is configured to detect the presence of an active
master server when newly connected to a corresponding virtual network on said shared
network and, if no active master server is detected, to become said active master
server; and
wherein, upon disconnection of said active master server, another said server
device becomes said active master server.
12. An apparatus as recited in claim 11, wherein said bandwidth within a given
priority group is assigned on an as-needed basis to virtual networks utilizing
up to their equal share of bandwidth within said given priority group, with additional
available bandwidth being equally divided between virtual networks with unfulfilled
bandwidth requests.
13. An apparatus as recited in claim 11, wherein said bandwidth is divided into
assignable time slots.
14. An apparatus as recited in claim 13, wherein one or more specific time slots
can be assigned when dividing bandwidth.
15. An apparatus as recited in claim 14, wherein said programming dynamically
reassigns time slots in response to changes in available bandwidth, the number
of streams being transmitted, and the priorities of the transmitted streams.
16. An apparatus as recited in claim 14, wherein said dynamic reassignment is
performed by an algorithm which is independently applied to each of said priority groups.
17. An apparatus as recited in claim 16:
wherein said algorithm is passed parameters comprising the requested number of
time slots per stream, the priority group for each stream, and the targeted total
number of slots allocated for each group;
wherein said algorithm returns the reassigned slot number for each stream, and
the total number of slots allocated as equal to or less than the targeted number.
18. An apparatus as recited in claim 16, wherein said algorithm comprises:
##EQU3##
δ(
x,y): Kronecker's delta function
δ(
x,y)=1 if
x=y;
δ(
x,y)=0 if
x≠y;
min(
x,y): minimum function
min(
x,y)=
x if
x≦y;
min(
x,y)=
y if
x>y;
##EQU4##
wherein k is the total network number; i is the network index (0≦i<k);
j is the stream index (0≦j<strm(i); T is the targeted total slot number;
p is the stream number of r(i)=1; strm(i) is the total stream number on network
i; r(i) is the reduction ratio of network i (0≦r(i)<1), wherein if
r(i) is 1, no reduction performed; s(i,j) is the slot number originally requested
by stream j on network i; and U(i) is the slot number originally requested by network i.
19. An apparatus as recited in claim 14, wherein said computer is configured
for communicating audio and/or video streams as received from stream input devices
and as transmitted to stream output devices, said input and output devices being
those connected to said virtual network.
20. An apparatus as recited in claim 14, further comprising encrypting data transmitted
over said virtual networks.
21. An apparatus as recited in claim 11, further comprising data storage within
said server device configured for recording and playing back audio and video streams.
22. An apparatus as recited in claim 21, wherein said server device is configured
as an audio and/or video server.
23. An apparatus as recited in claim 11, further comprising an output means integrated
with said server device and configured for playing audio and/or video streams.
24. An apparatus as recited in claim 11, further comprising an audio and/or video
tuner integrated with said server device and configured for receiving audio and/or
video streams from an antenna or cable connection.
25. An apparatus as recited in claim 11, further comprising a codec integrated
with said server device for encoding and decoding audio and/or video streams.
26. An apparatus as recited in claim 11, further comprising at least one user
interlace on said server device configured for controlling communications of audio
and video streams over said virtual network.
27. An apparatus as recited in claim 11, wherein said shared network comprises
a portion of a power line distribution system.
28. An apparatus as recited in claim 27, wherein each of said virtual networks
is associated with an individual dwelling, structure, or entity.
29. An apparatus as recited in claim 11, further comprising a remote communication
link on said server device configured for communicating with remote systems which
can not accessed over said shared network.
30. A system for managing bandwidth allocated to a plurality of virtual networks
on the same shared network, comprising:
a first server device connected to a virtual network on a shared network;
a second server device connected to another virtual network on said shared network;
said first and second server devices configured for communication with each other;
and
means associated with each said server device for dynamically allocating bandwidth
to each virtual network on said shared network to which said server devices are
connected, and for reallocating said bandwidth if sufficient bandwidth on said
shared network is not available to simultaneously support bandwidth requirements
of said virtual networks;
wherein at any given time a said one of said server devices functions as an active
master server;
wherein said active master server functions to reallocate said bandwidth if sufficient
bandwidth on said shared network is not available to simultaneously support bandwidth
requirements of said virtual networks;
wherein said server devices are configured to detect the presence of an active
master server when newly connected to a corresponding virtual network on said shared
network and, if no active master server is found, to become said active master
server; and
wherein, upon disconnection of said active master server, another said server
device becomes said active master server.
31. A system as recited in claim 30, wherein said shared network comprises a
power-line communication network.
32. A system as recited in claim 30, wherein said means for dynamically allocating
bandwidth is configured to allocate the available bandwidth across a set of priority
groups into which data streams are categorized on the basis of data stream content.
33. A system as recited in claim 32, further comprising means for establishing
a minimum amount of bandwidth to be allocated to each priority group.
34. A system as recited in claim 32, wherein data streams having an isochronous
nature are categorized into a high priority group, while data streams having an
asynchronous nature are categorized into a lower priority group.
35. A system as recited in claim 34, wherein said means for dynamically allocating
bandwidth is configured to categorize isochronous streams into group A or B, and
asynchronous streams into group C or D.
36. A system as recited in claim 35, wherein VoIP (voice over internet protocol)
and audio or video streams for live-recordings are categorized in group A, playback
of audio/video streams is categorized in group B, web accesses are categorized
in group C, and file transfers are categorized in group D.
37. A system as recited in claim 32, wherein said means for dynamically allocating
bandwidth is configured to fulfill all bandwidth requests of any virtual network
requesting up to its equal share of bandwidth within a given priority group, and
to equally share remaining bandwidth among virtual networks requesting more bandwidth
within a given priority group.
38. A system as recited in claim 30, wherein said means for dynamically allocating
bandwidth is integrated within a device selected from the group of audio and video
devices consisting essentially of set-top boxes, computer servers, television sets,
audio and/or video recording devices, and audio and/or video playback devices.
39. A system as recited in claim 30, wherein said means for dynamically allocating
bandwidth comprises:
a computer processor within a said device; and
programming executable by said computer processor for carrying out the operations
of
dividing the available bandwidth of the shared network into assignable units,
ordering streams, being transmitted over the shared network, into priority groups,
assigning units of bandwidth to said priority groups in response to the bandwidth
requirements of said streams end the transmission priority of said priority group,
and
assigning specific units of bandwidth to specific streams within each of said
priority groups in response to an equitable sharing of bandwidth between said virtual
networks shoring said shared network.
Description
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
Not Applicable
INCORPORATION-BY-REFERENCE OF MATERIAL SUBMITTED ON A COMPACT DISC
Not Applicable
NOTICE OF MATERIAL SUBJECT TO COPYRIGHT PROTECTION
A portion of the material in this patent document is subject to copyright protection
under the copyright laws of the United States and of other countries. The owner
of the copyright rights has no objection to the facsimile reproduction by anyone
of the patent document or the patent disclosure, as it appears in the United States
Patent and Trademark Office publicly available file or records, but otherwise reserves
all copyright rights whatsoever. The copyright owner does not hereby waive any
of its rights to have this patent document maintained in secrecy, including without
limitation its rights pursuant to 37 C.F.R. § 1.14.
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention pertains generally to power-line networks, and more particularly
to allocating bandwidth between virtual overlapping networks operating over the
same physical power-line network.
2. Description of Related Art
Power-line communication (PLC) is being increasingly adopted as a standard
network technology, in particular with regard to the consumer electronics market.
Products employing proprietary signaling formats have been known for some time,
and the current trends toward standardization have seen the marketing of standard
bridge, router, and other PLC network based products.
FIG. 1 illustrates a conventional PLC network shown connecting three homes H1,
H2, H3 to a distribution transformer, such as a 220 VAC service by
means of a neutral N and two phase legs L1 and L2. It can be seen
in the right of the figure how the power is distributed through a breaker panel
to individual outlets within the homes or offices.
FIG. 2 depicts an equivalent circuit representing the PLC network based within
the home power distribution example shown in FIG. 1. Resistive and capacitive
loads are shown distributed along the network. It will be readily appreciated from
viewing these figures that the homes share the PLC bandwidth and that data communicated
between PLC network connected devices within one home will be available for reception
at the other homes on the same segment of the power distribution grid, posing a
security threat.
Issues surrounding the use of PLC networking include both security and bandwidth
utilization. To overcome security issues it is most preferable to encrypt signals
being passed over the PLC network. Communication over the PLC network is facilitated
by giving each device connected to the PLC network a unique ID. Communication between
devices requires that the ID of a destination device be entered. The common key
is encrypted with the ID and sent to the first device. All the devices in the same
home share the same common key and encrypt communications with the key. A neighbor
cannot decrypt the communications without the common key, and each home (or entity
connected to a power line that shares a distribution transformer) uses its own
common key. A common key is therefore utilized for communicating between devices
on each virtual network and a unique ID (at least unique within the confines of
the virtual network) identifies each device within the virtual network.
The use of key based encryption is similar to encryption utilized within a VPN
(Virtual Private Network). In VPN, two remote nodes communicate through a public
network (i.e. the Internet) using encryption. Although only one physical network
exists, multiple overlapping virtual networks operate over it.
FIG. 3 illustrates multiple overlapping virtual networks on a power line, PL,
with three devices shown connected within a home establishing a first virtual network
I, another three connection nodes in another home establishing a second virtual
network II, and a final three devices on connection nodes in a third home establishing
a third virtual network III. It should be appreciated that the number of devices
on each virtual network may vary. With each virtual network configured with its
own common key, no communication typically takes place between the virtual networks.
As utilized herein the term "network" will be generally considered to mean a virtual
overlapping network, and not the physical network, unless specifically indicated.
The physical network is called the power line or the bus.
Another issue on present-day PLC network installations is access method.
Typically, CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance) is
utilized as it is in an Ethernet implementation. For a device to transmit, it first
senses the state of the network bus. If the bus is idle, the transmission may proceed.
If the bus is busy, transmission is deferred until the end of the current transmission.
After deferring to a transmission, the device starts priority contention followed
by a random backoff. CSMA/CA is simple and easy to connect, however, it is not
generally well suited for use with an isochronous transmission, such as AV stream
(audio and/or video stream), as it provides no guarantees that the data will be
sent to the destination within the time necessary for providing uninterrupted display
of the stream.
The use of multiple overlapping networks complicates the issue of access on CSMA/CA,
because CSMA/CA provides access on a first come first serve basis. Consequently,
the home that first accesses the PLC network could exclusively occupy a majority
of the PLC bandwidth, for example if communicating a high definition video signal
on the network. With a conventional CSMA/CA implementation, it is not possible
for those which subsequently access the network to recover bandwidth from those
which access it initially and retain their allotted bandwidth. This first-come
first-serve allocation does not provide an equitable arrangement for many network
applications, such as that of homes sharing the bandwidth of a power-line network
connecting to a single distribution transformer.
Utilizing the IEEE 1394 bus standard would guarantee isochronous communications,
however, it also provides bandwidth on a first-come first-serve basis. Therefore,
no device can take time slots by force when the bus bandwidth is fully occupied.
Furthermore, IEEE 1394 has no provisions for use on overlapping networks.
Therefore, a need exists for a system and method that provides equitable
bandwidth allocation on overlapping networks, such as multiple virtual networks
sharing a portion of a physical power-line. The present invention satisfies those
needs, as well as others, and overcomes the deficiencies of previously developed
power-line networking solutions.
BRIEF SUMMARY OF THE INVENTION
The present invention is directed toward managing the bandwidth available within
a common (overlapping) network shared by a plurality of virtual networks. The invention
is particularly well-suited for providing equitable sharing of the power-line bandwidth
on the same last-leg portion of the power distribution system shared among multiple
virtual networks, such as in neighboring homes with devices communicating over
the power-line network.
It is generally presumed herein that each device connected to the power-line
communications
network is capable of being identified as the destination or the source of a transmission
on the power-line network. The identification can be provided by encoding unit
IDs within transmissions, or utilizing any other convenient means for selecting
destinations and indicating the source of traffic.
The invention provides adaptive bandwidth management based on priority groups,
wherein streams that are considered higher priority are granted priority in obtaining
a desirable amount of bandwidth within a given priority group. The invention supports
both isochronous and asynchronous streams while allocating bandwidth in response
to the priority of the streams being communicated. Bandwidth allocations are based
on assigning time slots to each stream based on its priority, therefore allowing
each time slot to be used dynamically and efficiently. Higher priority streams
can be granted a larger number of time slots than lower priority streams.
Data streams to be communicated by transmitters over the respective virtual
networks are categorized within one of multiple priority groups (i.e. A, B, C,
D) based on intended data stream content. Bandwidth is made available to the groups
in priority order, however, even the lowest priority group is provided bandwidth
equal to or above a given minimum allocation. Each priority group is therefore
subject to being assigned at least a given minimum of time slots, or other bandwidth
allocation units. In this way low priority streams are not left waiting indefinitely
for usable bandwidth.
Bandwidth is assigned for data stream transmission within each virtual
network on the basis of need when virtual networks request up to their fair share
(quota) of bandwidth within the priority group. An "equal share" of bandwidth also
being referred to as quota which is defined herein as the amount of available bandwidth
within the priority group (i.e. number of slots) divided by the number of virtual
networks on the physical network. The bandwidth available from virtual networks
not using their full quota is equally shared amongst virtual networks with unfulfilled
bandwidth requests within the given priority group.
Network conditions on the PLC network can vary with respect to time, leading
to changes in the available bandwidth. The system is configured to dynamically
allocate bandwidth to streams. The number of time slots which can be assigned will
vary according to the available bandwidth, which can fluctuate in response to electrical
noise on the power-line or other conditions.
The system provides bandwidth allocations in a manner that is generally transparent
to the user. If, however, user bandwidth is cut dramatically the system is preferably
configured to notify the user. For example, a first user is passing high resolution
video streams over the network and utilizing the majority of the available bandwidth,
a second user then accesses the network and is fairly allocated bandwidth by the
system for their high definition stream, wherein the bandwidth provided to the
first user is reduced by the system of the present invention to accommodate a fair
bandwidth allocation to the second user. The system is configured so that it can
notify the first user of the drop in available bandwidth, and the user or the equipment
utilizing bandwidth on behalf of the user, can reconfigure bandwidth utilization
such as lowering the number of streams, framing rates, resolutions, and so forth.
Although the system may be implemented as a separate PLC control device,
it is preferably implemented in software executing on a device controlling power-line
access within a virtual network, such as upon an AV server controlling communication
within a household over a PLC network, or alternatively within a set-top box, computer
server, television set, audio and/or video recording device, audio and/or video
playing device, or other device configured for communicating and/or manipulating
audio and/or video streams. The system may comprise programming executable on a
computer device for carrying out the operations described herein. The programming
may be provided by way of a media containing the programming code which may be
executed on a computer. The system may contain hardware, including a computer element,
which can execute the programming.
The present invention may be generally considered an apparatus for managing bandwidth
allocated to virtual networks on an overlapping physical network, comprising: (a)
a device connected to a physical network and configured to communicate with at
least one other device connected to the physical network; and (b) means associated
with at least one device (connected on the network) for dynamically allocating
bandwidth to each virtual network on said physical network, and for reallocating
the bandwidth if sufficient bandwidth on the physical network is not available
to simultaneously support bandwidth requirements of the virtual networks.
Typically the means for dynamic allocation is provided by a programmable
element which executes programming for allocating bandwidth, by way of example
the programmable element may be a computer processor embedded within a device.
The programming categorizes isochronous data streams into groups of high priority
with asynchronous data streams being categorized into lower priority stream, wherein
the high priority stream receives priority with regard to receiving a requested
amount of bandwidth. To prevent bandwidth requests from lower priority streams
from being deferred indefinitely, the programming preferably comprises means for
establishing a lower limit on the amount of bandwidth to be allocated to a stream
of a given priority.
The programmable element may be implemented as a computer processor (CPU, microprocessor,
or similar element capable of executing programmed instructions) within a device
configured for communicating over said physical network with other devices. The
programming executing on the computer is configured for (a) dividing the available
bandwidth of the physical network into assignable units, (b) categorizing streams
for transmission over the physical network into priority groups, (c) assigning
sections of bandwidth (multiple bandwidth units that are preferably contiguous)
to the priority groups in response to the bandwidth requirements of the streams
and the transmission priority of the priority group, (d) assigning units of bandwidth
to specific streams within each of the priority groups in response to an equitable
sharing of bandwidth between the virtual networks sharing the physical network.
The preceding steps may also be considered a method of managing bandwidth allocated
to virtual networks on an overlapping physical network.
Quantization into bandwidth units is preferably performed in the system
with small enough bandwidth units to suit typical stream bandwidths while limiting
bandwidth waste. It should be recognized that streams requiring less than a unit
would require a full unit, while streams requiring just over one unit would use
two full units, in each case wasting almost a full unit of bandwidth. Therefore,
it is preferred that the bandwidth unit be selected of sufficiently small size
wherein typical streams require a number of bandwidth units, thus limiting bandwidth waste.
It will be appreciated that the computer processor may be retained in a separate
unit or integrated within a set-top box, computer server, television set, audio
and/or video recording device, or audio and/or video playback device. It will be
further appreciated that the programming executable on the computer for performing
the steps according to the present invention may be stored on a computer readable
media, or distributed by downloading, or other data communication means, without
departing from the teachings of the present invention.
A number of aspects of the present invention are described herein, it should
be
appreciated that these aspects may be implemented separately or in various combinations
thereof, without departing from the teachings of the present invention.
An aspect of the invention provides equitable bandwidth management for each virtual
network within a communication system supporting multiple overlapping virtual networks.
Another aspect of the invention prevents any one virtual network (i.e. home)
from monopolizing the available bandwidth when other virtual networks are requesting bandwidth.
Another aspect of the invention provides for adaptive bandwidth management
based on priority groups, wherein streams of higher priority are granted priority
toward obtaining a desired amount of bandwidth.
Another aspect of the invention provides for adaptive bandwidth management
wherein bandwidth requests from low priority streams are not deferred indefinitely.
Another aspect of the invention provides for adaptive bandwidth management
which takes into account varying bandwidth availability over time.
Another aspect of the invention provides adaptive bandwidth management which
integrates with AV dynamic rate control so that graceful stream degradation is
supported in response to lowering the bandwidth assigned to a given stream being
transmitted on the virtual network.
A still further aspect of the invention provides an adaptive bandwidth management
system that may be implemented in software within systems or devices controlling
virtual networks operating on the power line network.
Further aspects of the invention will be brought out in the following portions
of the specification, wherein the detailed description is for the purpose of fully
disclosing preferred embodiments of the invention without placing limitations thereon.
BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWING(S)
The invention will be more fully understood by reference to the following drawings
which are for illustrative purposes only:
FIG. 1 is a block diagram depicting a portion of a conventional power-line communication
(PLC) network showing a number of homes connected to a single power distribution transformer.
FIG. 2 is a schematic of a conventional power-line communication (PLC) network.
FIG. 3 is a node diagram of devices connected to a power-line communication
(PLC) network, showing each device belonging to one and only one of three virtual networks.
FIG. 4 is a block diagram of a portion of a power-line communication network
spanning two homes, showing servers and clients configured for communicating with
one another within each virtual network according to an aspect of the present invention.
FIG. 5 is a schematic of a server configured for communicating audio and video
streams over a power-line communications network according to an aspect of the
present invention.
FIG. 6 is a schematic of a display device configured for receiving audio and
video streams over a power-line communications network according to an aspect of
the present invention.
FIG. 7 is a flowchart depicting slot reassignment according to an aspect of
the present invention.
FIG. 8A is a flowchart depicting a minimum slot assignment process within bandwidth
management programming for a power-line communications network according to an
aspect of the present invention.
FIG. 8B is a flowchart which is a continuation of FIG. 8A.
FIG. 9 is a flowchart depicting a slot allocation process within bandwidth management
programming for a power-line communications network according to an aspect of the
present invention.
FIG. 10A is a flowchart depicting reassignment of time slots after stream terminations
according to an aspect of the present invention.
FIG. 10B is a flowchart which is a continuation of FIG. 10A.
DETAILED DESCRIPTION OF THE INVENTION
Referring more specifically to the drawings, for illustrative purposes
the present invention is embodied in the apparatus generally shown in FIG.
4
through FIG.
10B. It will be appreciated that the apparatus may vary as
to configuration and as to details of the parts, and that the method may vary as
to the specific steps and sequence, without departing from the basic concepts as
disclosed herein.
1. Detail of Network Bandwidth Management System and Method.
1.1 Power Line Network.
FIG. 4 shows an example of a power-line network
10. Distribution transformer
12 sends AC power over power-lines
14 to the power-line networks
16 and
18 within homes
20 and
22. In home
20,
a server
24 and client
26 are connected into power-line network
16.
Similarly, in home
22, a server
28 and client
30 are plugged
into power-line network
18. Unused AC power outlets are shown within house
20 to which additional powered devices may be connected for control over
the power-line network, or for conventional power distribution purposes.
From the perspective of network user's within each home
20,
22,
it appears that they have a private network for communicating over the power line
between the server and the devices. However, it is readily apparent from the figure,
that all these clients and servers communicate over a shared physical network extending
from the secondary of distribution transformer
12. Although only two homes
are shown connecting to the power-distribution transformer, in reality, several
homes typically share the output from a given power distribution transformer. As
a result, the operations of server
24 and server
28 and the devices
connected thereto are interdependent, and optimal fair sharing of the bandwidth
requires that servers
24 and
28 cooperate in controlling the use
of bandwidth within their respective virtual networks, in this case extending to
all power-line control devices connected within the specific home.
The present invention is configured for providing cooperative sharing of the
bandwidth within overlapping networks, such as overlapping virtual PLC networks.
The invention is configured to provide bandwidth management despite the effects
of power-line noise and unstable conditions on the power line. One preferred implementation
of the system is based on orthogonal frequency division multiplexing (OFDM) technology.
To establish stable connections on an unstable power-line medium, each device on
the power-line exchanges carrier information and best carriers are chosen each
time a communication is executed. Bandwidth is preferably managed based on a time
division multiple access (TDMA) mechanism, wherein bandwidth is parceled out as
time slot portions of the bandwidth. It should be appreciated that bandwidth may
be alternatively distributed as frequency ranges, or a combination of frequency
ranges and time slots, or other forms of packetizing available bandwidth for use
by streams. These alternative bandwidth distribution mechanisms may be adopted
without departing from the teachings of the present invention.
To simplify coordination between servers, the present system is preferably configured
to designate one of the servers, operating on the physical network bounded by the
distribution transformer, as a bus master. No special monopolistic operations are
accorded to the bus master and bus master selection may be determined in any convenient
manner. In the present embodiment, upon connecting a server to the power-line system,
the server attempts to detect the presence of a bus master. If no bus master is
found, then the newly connected server takes on the role of bus master. Upon disconnection
of an active master, another device operating on the power-line network will become
the new bus master. The master functions (according to a TDMA implementation) to
split the time axis into fixed length cycle frames, with each frame including a
fixed number of time slots.
The bus master preferably splits the available access time into fixed length
time cycles. A time cycle is divided to a fixed number of time slots, for example,
100 time slots. The master assigns one of more time slots to each stream. The time
slot(s) will be used for the stream every cycle until the stream terminates. To
start a stream, a sender requests time slots from the master. Since timing is critical
on isochronous streams, at least a certain number of time slots are reserved for
it. If bandwidth permits, then every stream obtains sufficient time slots as requested
to suit optimal operation, because sufficient time slots are available for allocation
by the master. However, if insufficient bandwidth exists for all streams, then
the master reassigns time slots to accomplish fair sharing between the virtual
networks within the stream group priorities. The master implemented according to
the present invention, therefore, reassigns time slots in an equitable sharing
arrangement for use by streams communicating within each virtual network sharing
the power line.
1.2 Server.
FIG. 5 depicts functionality within server
24 shown with internal bus
32. A tuner front-end
34 is configured for receiving a RF signal
from an antenna or a cable network. Codec block
36 in combination with memory
38 decodes the demodulated signal from tuner front-end
34. The decoded
digital video signal is then converted by conversion stage
40 for display
and/or audio output. By way of example, digital-to-analog conversion stages
42,
44 are depicted for generating analog signal outputs for driving a display
46 and audio system comprising amplifier
48 and audio transducer
50, such as one or more speakers. It should be appreciated that codec block
36 and converter stage
40 may be configured to support any desired
audio or video standard for playing an AV stream.
The AV stream can be transferred by codec
36 over bus
32 to a data
storage subsystem
52 for recording. Data storage subsystem
52 is
exemplified with a storage interface
54 shown connected to a hard disk drive
56. It will be appreciated that other forms of data storage may be utilized
additionally or alternatively in place of hard disk drive
56, for example
solid state storage, removable media storage, and so forth. To replay a recorded
stream, codec
36 receives the stream from data storage subsystem
52
over bus
32 and decodes it for output.
Server
24 can send or receive video streams over the PLC network from
clients which may comprise video imagers, display devices, recording and playback
devices, and the like. AV streams encoded on the AC power may be received through
AC power plug
58 to PLC interface
60 in conjunction with encryptor/decryptor
62, similarly AV streams may be transmitted in the reverse direction. For
example, an AV stream can be received from tuner front-end
34 and sent through
codec
36 by way of bus
32 to PLC interface
60 in combination
with encryption/decryption circuit
62, from where it is communicated by
AC power plug connection
58 over the power-line network
16 to client
26. Previously recorded streams may be accessed from data storage subsystem
52 and sent to the PLC interface
60 and encryption/decryption unit
62 for communication to client
26 over the power-line network
16.
Streams may be received from clients over the PLC network into PLC interface
60
and encryption/decryption unit
62, which are passed through bus
32
to Codec
36 for playback, or recorded (fully or partially) on the data storage
system
52.
It should be appreciated that multiple data storage elements may be supported
within the present invention, such as a hard disk drive used in combination with
a removable media drive (i.e. writable optical DVD drive), allowing rapid archival
access to data and streams. To ensure security of the virtual network connections
over the physical power-line distribution network which is typically bounded by
a distribution transformer, PLC interface
60 is shown in combination with
encryption/decryption unit
62, which is preferably provided to encrypt data
prior to transmission and to decrypt data that has been received.
User control of server
24 may be provided within the system by any convenient
method. By way of example, input commands are depicted being received through a
command interface
64 from a user input device
66, such as a keypad,
keyboard, discrete buttons, cursor control device (pointing device), other input
sources and combinations thereof. Server operations may be remotely controlled
through a wireless interface
68, receiving input from a wireless device
70, such as a remote control unit utilizing infrared (IR) communication,
wireless communication, and so forth.
Commands received through interfaces
64,
68 are communicated
over bus
32 to a control unit, central processor
72 that operates
in conjunction with memory
74. Programming according to the present invention
may be stored within memory
74 for execution by central processor
72.
It should be noted that the present invention may be implemented as programming
that executes within conventional video hardware supporting a power-line interface
and the requisite hardware elements to support the desired applications.
Additional communication channels may be supported on client
24
for communicating with local devices on separate wing or wireless links, or for
communicating to remote devices located beyond the last leg section of a power-line
network. By way of example, remote communication may be supported by modem
76,
which may be provided by any form of communication modem or gateway, although high
speed connections such as through a cable modem or an xDSL modem are preferred.
The remote communication channel is particularly well suited for communicating
data and streams from, and to, a wide area network, such as the Internet.
1.3 Client.
FIG. 6 depicts functionality within a representative client
26 having
internal bus
78. A central processor
80 in combination with memory
82 is shown for controlling each component over bus
78. Programming
executable on central processor
80 controls the hardware of client
26
according to the functions of the present invention. Additionally, memory
82
may retain variables, buffers, temporary data storage, and so forth. An AC power
plug connection
84 is shown connecting to the power-line and routing signals
to a PLC interface
86 in combination with encryptor/decryptor
88.
Signals received over the PLC network through PLC interface
86 are passed
to decoder
90 in combination with memory
92, prior to being output
to the user. The decoded digital video signal is then converted by conversion stage
94 for display and/or audio output. By way of example, digital-to-analog
conversion stages
96,
98 are depicted for generating analog signal
outputs for driving a display
100 and audio system comprising amplifier
102 and audio transducer
104, such as one or more speakers. It should
be appreciated that decoder
90 and converter stage
94 may be configured
to support any desired audio or video standard for playing an AV stream.
User interfaces may be supported on client
26 in a similar manner as
they are supported on the server. An interface
106 is preferably provided
to an input device
108, such as a keypad, keyboard, discrete buttons, cursor
control device (pointing device), other input sources and combinations thereof.
Client operations may be remotely controlled through a wireless interface
110,
receiving input from a wireless device
112, such as a remote control unit
utilizing infrared (IR) communication, wireless communication, and so forth.
Although client
26 is shown for receiving a stream over the power-line
network, it will be appreciated that clients may be alternatively, or additionally,
configured for transmitting video streams, such as from a video imaging device,
or other forms of data.
1.4 Network Communication.
Consider the situation in which it is desirable for server
28 to
send a data stream to client
30. The present invention generally refers
to the data being passed over the PLC network as a "stream", however it should
be appreciated that other forms of data may be passed in conjunction with or as
an alternative to a stream. Stream data may be generally considered isochronous,
asynchronous, or a combination of the two. The transmitter, server
28, requests
from the master (server
24) sufficient time slots to send the stream. The
request must be handled by the master as it manages the allocations of the available
time slots. The master returns a response to inform the transmitter of the time
slots it is being assigned. The transmitter commences stream transmission using
the assigned time slots. It will be appreciated that the master adjusts the slots
available for assignment in response to changes in available bandwidth, requests
for bandwidth, and prioritization of bandwidth requests.
For example, as the bus becomes so busy in response to bandwidth requests that
not all bandwidth requests can be simultaneously fulfilled, then the master may
assign fewer time slots to a stream than requested by the transmitter. In this
case, the transmitter must adjust its data encoding rate to fit the given bandwidth.
After the transmitter terminates the stream, it informs the master that the given
time slots are no longer in use, whereas the master reassigns the time slots to
other streams. For slot management communications, one or more time slots may be
reserved and are thus not available at any time for carrying isochronous or asynchronous
streams. The following sections describe how the master manages time slots.
2. Time Slot Reassignment Algorithm.
2.1 Priority Groups.
Before a device transmits a new stream, it requests time slot assignments
from the master. In response, the master assigns time slots to the device, yet
is not always able to assign the number of time slots requested by the transmitting
device. If insufficient time slots are available for use, then the master reassigns
slots based on the network priority and the priority of the stream.
By way of example, the present invention may be configured with four priority
levels, group A, B, C and D. Group A has the highest priority and group D has the
lowest. An isochronous stream is categorized to group A or B, while an asynchronous
stream is categorized to group C or D. For example, VoIP (Voice over IP) and a
live-recording audio or video stream are categorized in group A. It will be appreciated
that since it is impossible to retrieve live-recording data, it should be given
the highest priority. A playback audio/video stream is considered to be in group
B. Web accesses are provided for in group C, while file transfer are considered
to be in group D. It should be recognized that different implementations of the
system may define these priority groups in different ways without departing from
the teachings of the present invention. The present invention is preferably configured
for allocating a guaranteed minimum number of time slots for a request according
to each group under any condition so that even low priority streams are regularly
serviced, albeit with a small bandwidth allocation.
2.2 Network Priority.
Several virtual networks may operate on a single physical power-line network,
as a number of homes may share a given power distribution transformer. The practice
of allocating bandwidth on a first-come, first-serve basis is not equitable in
the present PLC network application or in similar situations of overlapping virtual
networks, because the first user may monopolize more than their fair share of the
bandwidth constraining the operation of peers attempting to communicate over the
network. Consider an example, wherein a first home is utilizing 95% of the entire
power-line bandwidth, as a second home accesses the network and requires 20% of
the bandwidth. Under a first-come first-serve basis the user at the first home
may continue to monopolize the bandwidth, while the second home is unable to obtain
sufficient bandwidth for their desired operation.
In contrast, the present invention fairly allocates bandwidth to solve this problem.
Time slot portions of the bandwidth are assigned according to need up to an equal
share of available bandwidth, after which available bandwidth is divided equally
among those requesting additional bandwidth. Reallocations are performed to dynamically
adjust bandwidth allocation in response to new bandwidth requests, stream terminations,
overall physical network bandwidth changes, and so forth.
2.3 Time Slot Reassignment.
The method of allocating bandwidth within the present invention is based on time
slots which can be assigned or reassigned to each request on the virtual network.
The time slots are preferably allocated in response to the priority of the data
(i.e. stream) to be transmitted. The assignment/reassignment is performed within
the present invention by a time slot reassignment algorithm which is substantially
applied independently to each priority group.
Parameters are input to the algorithm, preferably including:
- (a) requested number of time slots per each stream;
- (b) priority group name of each stream (i.e. group A, B or Q);
- (c) targeted total number of slots for each group.
The algorithm returns:
- (a) reassigned slot number for each stream;
- (b) total number of slots for each group allocated as equal to or less
than the targeted number.
If insufficient time slots are available to meet the requirements for the group,
then a time slot reduction is performed. In this case all or some of the streams
are then assigned fewer time slots than have been requested. When slot reduction
is required, the master is configured to preferably send a command/notification
of the time slot reductions to the stream transmitter. When the stream is rate
adjustable, such as for certain audio or video streams, the transmitter reduces
the encoding rate to fit the new narrower available bandwidth (according to the
fewer time slots allotted) thus providing graceful degradation in response to lowered
bandwidth. When a stream is not rate adjustable, for example an asynchronous stream,
no rate adjustment is performed, because the reduction in available time slots
only causes a slowdown or a halt in the stream transfer.
Parameters of the time slot reassignment algorithm may be defined as follows:
k—total network number;
i—network index (0≦i<
