 |
Description  |
|
|
TECHHICAL FIELD
The present invention relates generally to managing bandwidth resources
within a switching communication network, and more particularly, to
managing bandwidth resources within a switching communication network
having at least one fast packet switch.
BACKGROUND ART
Fast packet switching is an emerging multiplexing and switching technique
used in cell relay services, such as the asynchronous transfer mode (ATM)
technique, and frame relay services. Briefly, fast packet switching is a
technique wherein a message is communicated between a source endpoint and
a destination endpoint of a switching network using a series of
information passing elements, i.e. packets, each of which contain both a
payload field and an address field. The switching network used for
connecting the two endpoints is composed of one or more fast packet
switches with transmission facilities connecting the switches. Each of the
fast packet switches contains a plurality of switch ports between which
packets are communicated via a self-routing switching fabric. As a result,
each of the switch ports can be employed either as a connection to an
endpoint or as a connection to another fast packet switch in the network
via the transmission facilities.
Each message to be communicated using fast packet switching is packetized
by dividing the message into one or more pieces of information. Each of
the pieces of information is loaded into the payload field of a
corresponding packet. In a frame relay service, the packets are referred
to as frames, and the length of the payload field is variable. In
contrast, the length of the payload field is fixed in a cell relay
service, wherein the packets are referred to as cells. Regardless of the
type of packet employed, each of the packets is further loaded with an
address field which contains information identifying a provisioned virtual
connection between the two endpoints. Typically, the address field is
contained in a header in the packet.
The packets are then forwarded to the switching network at the source
endpoint for transmission to the destination endpoint. The switching
network routes the packets to the destination endpoint based upon routing
data in the fast packet switches. The routing data is written into the
fast packet switches by a connection management processor at the time the
virtual connection is provisioned. In particular, the routing data
specifies how a packet is to be routed through the network based upon
information contained within the address field of the packet.
Presently, a traffic contract for each virtual connection is negotiated,
between a subscriber and a provisioning agent who represents the network,
at the time of provisioning or subscription. The terms of the contract
include a constraint on the amount of bandwidth which can be used by the
subscriber on the virtual connection. The measure of the amount of
bandwidth used by a virtual connection can be based upon a measure of the
mean bit rate, the peak bit rate, and/or the duration at which the peak
rate is sustained, to name a few commonly-used parameters.
In accordance with the negotiated traffic contract, the connection
management processor writes bandwidth parameters into the fast packet
switches, wherein the bandwidth parameters are representative of bandwidth
usage associated with each provisioned connection provided by the switch.
Thereafter, each virtual connection is monitored within each switch for
possible contract violations.
An example monitoring scheme utilizes what is referred to in the art as a
"leaky bucket". A leaky bucket is a counter which is incremented upon an
arrival of a packet, and is decremented periodically. If an incoming
packet causes the counter to exceed a predetermined threshold, the
contract is considered to be violated.
Regardless of the monitoring scheme employed, the network penalizes packets
which violate the contract. For example, the network can discard the
violating packets, or mark the violating packets with a low priority for
loss. In this manner, the network can allocate bandwidth for the virtual
connection and guarantee that the subscriber using the connection does not
exceed the bandwidth parameters, which could result in interfering with
other customers sharing bandwidth in the network.
Disadvantages of the present approach of associating a corresponding
bandwidth constraint with each virtual connection become evident when
implementing a virtual private network (VPN). A virtual private network is
implemented for a plurality of subscribers by provisioning a plurality of
permanent virtual connections such that each subscriber is permanently
virtually connected to each other subscriber. If N subscribers are to be
fully interconnected in a virtual private network, i.e. each subscriber is
capable of transmitting information to each other subscriber, N(N-1)
one-way virtual connections are required (one connection from each of N
subscribers to the N-1 others). Since every connection has a corresponding
cost commensurate with bandwidth allocated and associated therewith, the
cost of implementing a virtual private network may be prohibitive for
larger numbers of subscribers.
SUMMARY OF THE INVENTION
It is an object of the present invention to reduce bandwidth requirements
in a communication network having at least one fast packet switch.
It is an object of the present invention to reduce the cost of implementing
a virtual private network.
In carrying out the above objects, the present invention provides a method
of resource management in a fast packet switching communication network.
The method comprises a step of receiving a packet having an address field
which identifies a source endpoint and a destination endpoint. The method
further comprises a step of enforcing a bandwidth constraint based upon
the source endpoint identified by the address field, wherein the bandwidth
constraint is enforced independently of the destination endpoint.
Further in carrying out the above objects, the present invention provides a
method of resource management in a communication network having at least
one fast packet switch, wherein a plurality of virtual connections are
provisioned from a source endpoint to a plurality of destination
endpoints. The method comprises a step of receiving a packet having an
address field which identifies one of the plurality of virtual
connections. The method further comprises a step of enforcing a bandwidth
constraint for the plurality of virtual connections based upon a measure
of the bandwidth usage associated with the source endpoint over all of the
plurality of virtual connections.
Still further in carrying out the above objects, the present invention
provides systems for resource management which perform the steps of the
above-mentioned methods.
These and other features, aspects, and advantages of the present invention
will become better understood with regard to the following description,
appended claims, and accompanying drawings.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a flow chart of an embodiment of a method of resource management
in a fast packet switching network;
FIGS. 2a and 2b illustrate examples of packets having a protocol in
accordance with the present invention;
FIG. 3 is a block diagram of a fast packet switch having an embodiment of a
system for bandwidth resource management in accordance with the present
invention;
FIG. 4 is a flow chart of a method of processing a received packet for use
with embodiments of the line unit in accordance with the present
invention;
FIG. 5 is a block diagram of a communication network in accordance with
embodiments of the present invention;
FIG. 6 is a schematic block diagram of an embodiment of a ring network in
accordance with embodiments of the present invention;
FIG. 7 is a block diagram of a ring network used for performing a routing
cost analysis;
FIG. 8 is a block diagram illustrating connection costs measured in terms
of transmission segments;
FIG. 9 is a block diagram illustrating the transmission segments used for a
unidirectional bundle from a single subscriber to all other subscribers in
a network;
FIG. 10 is a graph of routing costs for an embodiment of the present
invention compared with other materials;
FIG. 11 is a block diagram of an embodiment of a system for controlling a
flow of packets being forwarded by a customer premises equipment to an
endpoint of a fast packet switching network; and
FIG. 12 is a flow chart of an embodiment of a method of controlling a flow
of packets being forwarded by a customer premises equipment to an endpoint
of a fast packet switching network.
BEST MODE FOR CARRYING OUT THE INVENTION
Briefly, embodiments of the present invention overcome the above-described
shortcomings of previous resource management methods and systems in that
bandwidth is not associated with each virtual connection. Instead,
bandwidth is associated with each source endpoint independent of the
number of virtual connections emanating from the source endpoint to
potential destination endpoints. As a result, the virtual connections to
all of the potential destination endpoints are bundled together for the
purpose of assigning and associating bandwidth. Consequently, the cost of
implementing a virtual private network wherein N-1 virtual connections
emanate from each source endpoint, and wherein each source transmits on
one of the N-1 virtual connections at a time, can be reduced using
embodiments of the present invention.
FIG. 1 is a flow chart of an embodiment of a method of resource management
in a fast packet switching network. The fast packet switching network,
having a plurality of endpoints, includes at least one fast packet switch
used in providing a virtual connection between at least one selected pair
of the endpoints. The method includes a step of receiving a packet having
an address field which identifies a source endpoint and a destination
endpoint, as indicated by block 10. Typically, the step of receiving the
packet is performed at a switch port in a fast packet switch within the
network.
The address may identify, but need not identify a unique global address of
the user at the source and destination endpoints such as a telephone
number. In a preferred embodiment, the address identifies a hop or segment
of a virtual connection in a network of fast packet switches. Translations
in a fast packet switch may change the address in the packet for
subsequent hops of the same virtual connection. In other words, the
address locally identifies a virtual connection, and is uniquely
associated with, and therefore indirectly identifies, the source and
destination endpoints connected.
In one embodiment, the packet does not contain any unique label which
directly identifies the source. The packet only contains a virtual
connection identifier indirectly associating a source and destination
pair. A lookup of the virtual connection identifier in a database or
translation table can be used to directly identify a source. A number of
virtual connections identifiers may have one source associated with them
in the database if that source has virtual connections to many
destinations.
Preferably, the address field contains a source label which identifies the
source endpoint and a destination label which identifies the destination
endpoint, although alternative embodiments of the present invention are
not limited thereto. The source label and the destination label uniquely
identify a source endpoint-destination endpoint pair, and thereby uniquely
identify a unidirectional virtual connection between the pair.
An example of a packet 20 having a protocol in accordance with the present
invention is illustrated in FIG. 2a. The packet 20 includes a payload
field 21 and an address field 22. The address field 22 includes a
source-associated part 23 and a destination-associated part 24. The
address field 22 is contained within a header of the packet 20.
Hereinafter, an address field in accordance with this protocol is referred
to as a virtual connection identifier label (VCIL).
Another example of a packet having a protocol in accordance with the
present invention is illustrated in FIG. 2b. Here, the packet comprises a
fixed-length cell 25 based upon the ATM standard. The cell 25 includes a
48-octet payload field 26 and a 5-octet header 27. The header 27 includes
the following fields:
a generic flow control (GFC) field, a virtual path identifier (VPI) field,
a virtual channel identifier (VCI) field, a payload information type (PT)
field, a cell loss priority (CLP) field, and a header error control (HEC)
field. In a preferred embodiment, the address field is comprised of the
VPI field and the VCI field within the header. More preferably, the VPI
field is used for identifying the source endpoint, and the VCI field is
used for identifying the destination endpoint.
It is noted that the packet protocols illustrated in FIG. 2 are examples of
many types of protocols which can be employed using embodiments of the
present invention. In particular, the present invention can be applied to
frames as well as cells. Further, the cells are not necessarily limited to
the ATM standard.
Referring back to FIG. 1, the method further includes a step of enforcing a
bandwidth constraint, as indicated by block 12, based upon the source
endpoint identified by the address field, wherein the bandwidth constraint
is independent of the destination endpoint identified by the address
field. In a preferred embodiment wherein the address field contains a
source label which identifies the source endpoint and a destination label
which identifies the destination endpoint, the bandwidth constraint is
enforced based upon the source label and is independent of the destination
label.
In a second embodiment, only a virtual connection is identified. A database
or translation table lookup identifies the source transmitting on that
virtual connection. The bandwidth constraint is enforced based upon the
source thus identified.
The bandwidth constraint is based upon at least one predefined measure of
the bandwidth associated with the source identified by the address field.
As previously mentioned, such measures of bandwidth include average bit
rate and peak bit rate. If the bandwidth constraint for the source
endpoint is violated by an incoming packet in accordance with a
predetermined traffic contract, then the packet is penalized in a
predetermined manner. As described earlier, the violating packet can be
discarded or marked with a low priority for loss, for example.
Based upon whether or not the packet violates the bandwidth constraint and
the type of penalty employed for violating packets, the method may further
include a step of routing the packet based upon the address field, as
indicated by block 14. Here, the packet is routed from the switch port at
which the packet is received, through the switching fabric contained
within the fast packet switch, to a second port for transmission toward
the destination endpoint. As one with ordinary skill in the art will
recognize, the destination endpoint may be located at a switch port on
another fast packet switch connected to the second port via a transmission
facility, and as such may not be directly interfaced to the second port.
In a preferred embodiment, wherein the address field contains a source
label which identifies the source endpoint and a destination label which
identifies the destination endpoint, the step of routing the packet is
based upon both the source label and the destination label. An example of
when the packet may not be routed through the switching fabric is when the
packet is discarded in the step of enforcing the bandwidth constraint.
The method of FIG. 1 can be employed to provide bandwidth resource
management in a communication network wherein a plurality of virtual
connections are provisioned from a source endpoint to a plurality of
potential destination endpoints, and wherein the desired destination
endpoint identified by the address field of the received packet is
included in the plurality of potential destination endpoints. It is noted
that the address field need not explicitly identify the desired
destination endpoint; for example, the address field may identify the
virtual connection between the source endpoint and the desired destination
endpoint. Here, the desired destination endpoint can be found from a
database based upon the virtual connection identified by the address
field.
The bandwidth constraint for the source endpoint is enforced by measuring
the bandwidth usage associated with the source endpoint over all of the
plurality of virtual connections. If the packet causes the violation of a
predetermined bandwidth constraint, then the packet is penalized as
described earlier. In this context, the plurality of virtual connections
which emanate from the source endpoint can be considered as a bundle for
the purpose of assigning bandwidth thereto and enforcing bandwidth
constraints therefor.
FIG. 3 is a block diagram of a fast packet switch 30 having an embodiment
of a system for bandwidth resource management in accordance with the
present invention. The fast packet switch 30 includes a plurality of
switch ports 32, each of the switch ports 32 providing a port either to
some type of subscriber equipment (for communication with the subscriber)
or to a transmission facility (for communication with another switch in a
network). It is noted that subscriber equipment refers generally to any
type of equipment which a subscriber may employ at an endpoint of the
network. Examples of subscriber equipment include, but are not limited to,
phone equipment, a router or other datacom equipment, a private branch
exchange (PBX), or an interface to another network.
Each of the switch ports 32 (or each transmission facility) has a line unit
34 associated therewith. Each line unit 34 performs two main functions:
(i) it processes the physical layer protocol, and (ii) it processes the
packet protocol. A physical interface 36 performs the physical layer
protocol processing. As such, the physical interface 36 provides means for
receiving and transmitting electrical signals representative of received
and transmitted packets.
A packet protocol processor 37 performs the packet protocol processing. The
packet protocol processor 37 provides means for enforcing a bandwidth
constraint based upon an address field contained within the received
packet. Consequently, the line unit 34 enforces a bandwidth constraint for
packets communicated over a bundle of provisioned virtual connections
emanating from a source endpoint identified by the address field. As
described earlier, a received packet which violates the bandwidth
constraint is penalized in a predetermined manner.
Based upon whether or not the received packet violates the bandwidth
constraint, and the type of penalty employed for violating packets, the
line unit 34 further provides the packet a physical switch port address to
a self-routing switching fabric 38. The fabric 38 delivers the packet to a
selected one of the switch ports 32 identified by the physical switch port
address. Once delivered to the selected switch port, the packet can be
transmitted to another switch in the network or to equipment at a
subscriber endpoint. The physical switch port address can be discarded at
the selected output switch port.
FIG. 4 is a flow chart of a method of processing a received packet for use
with embodiments of the line unit in accordance with the present
invention. Upon receiving the packet, the address field, typically located
in a header in the packet, is extracted as indicated by block 40.
The bandwidth parameters associated with the source endpoint identified by
the address field are obtained from a look-up table, as indicated by block
42. The bandwidth parameters provide measures of the bandwidth associated
with a bundle of provisioned virtual connections emanating from the source
endpoint.
As indicated by block 44, the bandwidth parameters for the source endpoint
are examined for violations with respect to a predetermined traffic
contract for the bundle of virtual connections emanating from the source
endpoint. If at least one of the bandwidth parameters is in violation of
the traffic contract, then the packet is discarded, as indicated by block
46, and the bandwidth parameters in the look-up table are updated
accordingly, as indicated by block 50.
If the traffic contract is not violated, then a new outgoing address field
and a physical switch port address are obtained by the look-up table, as
indicated by block 54. Two embodiments of performing this step are
described below.
In a first embodiment, the new outgoing address field and the physical
switch port address are obtained from the look-up table in dependence upon
a concatenated address comprising the source label and the destination
label. This table look-up returns the physical switch port address and a
full, new outgoing address field having a new source label and a new
destination label.
In a second embodiment of a method of performing the step indicated by
block 54, an intermediate pointer label is obtained from the look-up table
in dependence upon the source label. The intermediate pointer label and
the destination label are then concatenated. A second table look-up step
is performed based upon the concatenated label. This returns the physical
switch port address as well as a new outgoing address field.
As indicated by block 56, the method further includes a step of modifying
the address field of the packet to include the new outgoing address. As
indicated by block 60, the method includes a step of appending the
physical switch port address to the front of the packet. The packet is
then sent to the switch fabric, as indicated by block 62.
The switch fabric uses the physical switch port address to route the packet
therethrough. Once the switch fabric is traversed, the port address is
discarded. The packet can then be transmitted on a transmission facility
to another switch in the network with the new outgoing address field in
the packet header.
As indicated by block 64, the step of updating the bandwidth parameters in
the look-up table is performed. The bandwidth parameters are updated
according to the contribution of the current packet to the measurement of
the average and peak bandwidth.
In order to illustrate the utilization of embodiments of the present
invention and advantages which result therefrom, a block diagram of an
example communication network in accordance with the present invention is
given in FIG. 5. For the purpose of illustration, the network includes
three representative fast packet switches 70, 72, and 74. The fast packet
switch 70 communicates with the fast packet switch 72 via a transmission
facility 76. Similarly, the fast packet switch 72 communicates with the
fast packet switch 74 via a transmission facility 80.
The fast packet switch 70 provides three illustrated endpoints 82a, 82b,
and 82c of the network. Similarly, the fast packet switch 72 provides two
illustrated endpoints 82d and 82e, and the fast packet switch 74 provides
three illustrated endpoints 82f, 82g, and 82h. Subscribers are interfaced
to the endpoints 82a-82h of the network by a corresponding one of
subscriber equipment 84a-84h. A connection management processor 86, which
performs functions as earlier described, is coupled for communication with
the fast packet switches 70, 72, and 74.
Suppose that the endpoint 82a has five virtual connections emanating
therefrom, one virtual connection to each of endpoints 82d-82h (i.e., 82a
to 82d, 82a to 82e, 82a to 82f, 82a to 82g, and 82a to 82h). Further,
suppose that endpoints 82b and 82c each has five virtual connections
emanating therefrom in a similar manner. Consequently, a total of 15
virtual connections emanate from the fast packet switch 70. However,
assuming that each of the endpoints 82a-82c can transmit to only one
destination endpoint at a time, only three transmissions can take place at
a time from the fast packet switch 70 via the transmission facility 76.
Using embodiments of the present invention, bandwidth use is monitored and
enforced for each of the three source endpoints 82a-82c rather than for
each of the 15 virtual connections. In terms of the bundling terminology:
the five virtual connections from the endpoint 82a are considered as a
first bundle; the five virtual connections from the endpoint 82b are
considered as a second bundle; and the five virtual connections from the
endpoint 82c are considered as a third bundle. As a result, less bandwidth
needs to be allocated in the transmission facility 76 to provide the 15
virtual connections in three bundles, in comparison to having 15
provisioned virtual connections each having bandwidth associated
therewith.
Embodiments of the present invention are further illustrated in terms of a
virtual private network, which is to be implemented for a plurality of
subscribers. First, the network is provisioned with virtual connections
between all subscriber endpoints. This consists of writing data into all
the fast packet switches associating addresses and bandwidth parameters
with all the virtual connections. This is performed by the network
managers. When a transmission of information is to be made from a first
subscriber to a second subscriber, the first subscriber packetizes the
information, and includes the proper address field in a header of each
packet. For two-way communications, the second subscriber packetizes its
information to be sent to the first subscriber, and includes the proper
address field in the header of each packet. The proper address field can
be found by the subscriber in the following two ways.
In a first method, a table is provisioned in each piece of subscriber
equipment by the network manager at network provisioning time. The table
in each subscriber equipment contains the address of each other
subscriber, and associated with it, the address field to be used to
communicate between the subscriber and any of the other subscribers.
In a second method, all of the subscribers are provisioned a virtual
connection to communicate to a common database, which acts as a name
server. If a first subscriber wishes to communicate with a second
subscriber, the first subscriber sends a packet to the database to query
which VCIL to use in the address field of packets to be transmitted to the
second subscriber. The database responds with a query packet containing
the address of both the first subscriber and the second subscriber. The
database communicates, to the first subscriber, the VCIL to be used for
both ways of two-way communications between the first subscriber and the
second subscriber. Thereafter, the first subscriber may send a control
packet to the second subscriber to tell of his/her intent to begin
communication as well as the VCIL to use on a return path.
The following examples pertain to embodiments of the present invention for
use in ATM applications. Hereinafter, methods and systems for bandwidth
management in ATM applications in accordance with the present invention
are referred to as BABM (bundled ATM bandwidth management).
FIG. 6 illustrates a ring network configuration similar to networks
currently deployed in a local exchange carrier (LEC). The network
virtually connects a source terminal 100 to six destination locations
102a-102f. In practice, the source terminal 100 may be an information
server, a network element such as a private branch exchange, or a customer
premises equipment. The network includes a fast packet switch 104 which is
responsive to cells transmitted by the source terminal 100. The fast
packet switch 104 is capable of performing a user parameter control (UPC)
function on a bundle comprised of the six virtual connections. The UPC
function is performed to check that the traffic conforms to contracted
parameters. In general, each bundle is defined by a unique VPI value. The
network further includes three cross-connect switches 106a-106c used for
dropping off each cell at a desired one of the destination locations
102a-102f based on a VPI/VCI combination in the header of the cell.
If one wanted to establish bidirectional transmission capabilities, i.e.
including transmissions from the six destinations 102a-102f to the source
terminal 100, similar unidirectional bundles of virtual connections must
be established.
In a first illustrative example, the source terminal 100 is an Ethernet
adaptor used as a public network gateway from a private business location.
The Ethernet adaptor adapts Ethernet traffic to ATM for public network
connection to the six destination locations 102a-102f, which may represent
six other business locations. The six destinations 102a-102f are
identified by six VCIs ranging from 10 to 15. All connections are bundled
in a virtual path identified by VPI=15.
The VPI is provisioned to be accessible to all nodes in the network with 10
Mb/s of bandwidth peak rate allocated thereto. Peak rate allocation means
that the average bandwidth and the peak bandwidth on the VPI are the same
and are both set to 10 Mb/s in this case. Since the peak and average are
the same, the network is in essence set up for a Constant Bit Rate (CBR)
service of 10 Mb/s on the VPI. Though the Ethernet source may in fact
exhibit burstiness by sending 10 Mb/s so | | |
