United States Patent 19
`Teraslinna
`
`US00562.3492A
`Patent Number:
`11
`(45) Date of Patent:
`
`5,623,492
`Apr. 22, 1997
`
`54 METHODS AND SYSTEMS FOR MANAGING
`BANDWDTH RESOURCES IN A FAST
`PACKET SWITCHING NETWORK
`
`75 Inventor: Kari Teraslinna, Boulder, Colo.
`a
`(73) Assignee: U S West Technologies, Inc., Boulder,
`Colo.
`
`OTHER PUBLICATIONS
`"The Asynchronous Transfer Mode: a tutorial', Jean-Yves
`Le Boudec, Computer Networks and ISDN Systems 24
`(1992), pp. 279-309.
`Paper on "Requirements for Phase 2 Signaling Protocol",
`ATM Forum Technical Committee Meeting; Jan. 17-20,
`1994.
`
`(21) Appl. No.: 410,369
`(22
`Filed:
`Mar. 24, 1995
`(51) int. Cl. .................... H04J 3/24
`52 U.S. C. ............................................. 370/397; 370/468
`58 Field of Search ................. 370/60, 60.1, 58.1-58.3,
`370/94.1, 94.3, 17, 118, 94.2, 15, 16, 110.1,
`112, 85.2
`
`56)
`
`a f Vs
`
`OTT Clal. ................................
`
`References Cited
`U.S. PATENT DOCUMENTS
`3. Y: se al. ................. : I
`5,280,470
`1/1994 Buhrke et al.
`... 370/942
`370/60.1
`5,285,446 2/1994 Yonehara ......
`5,303,233 4/1994 Sugawara......
`- 370/60
`-
`-
`... 370/60.1
`5,432,783 7/1995 Ahmed et al. .....
`5,442,624 8/1995 Bonomi et al. ........................... 370/17
`5,448,559 9/1995 Hayter et al. .......................... 370/60.1
`
`Primary Examiner-Douglas W. Olms
`Assistant Examiner-Ajit Patel
`Attorney, Agent, or Firm-Brooks & Kushman
`
`ABSTRACT
`(57) .
`Methods and systems for resource management in a fast
`packet switching communication network are disclosed. A
`packet containing an address field identifying a source
`endpoint and a destination endpoint is received. A band
`width constraint based upon the source endpoint, but inde
`pendent of the destination endpoint, is enforced for the
`packet. In a communication network wherein a plurality of
`virtual connections are provisioned from a single source
`endpoint to a plurality of destination endpoints, the band
`width constraint is associated with bandwidth usage over all
`of the virtual connections.
`
`-
`
`6 Claims, 6 Drawing Sheets
`
`54
`
`56
`
`EXTRACT ADDRESS FELD
`
`OBTAN BANDWDTH PARAMETERS
`FROM LOOK-UP TABLE BASED
`UPON SOURCE ENDPOINT
`
`40
`
`42
`
`
`
`
`
`44
`
`
`
`PASS
`BANDWIDTH
`PARAMETER
`CONTROLS
`YES
`
`NO
`
`GET NEW OUTGONGADDRESS
`FIELD AND PHYSICAL SWITCH
`PORT ADDRESS FROM TABLE
`
`DISCARD
`PACKET
`
`UPDATE PARAMETERS
`N LOOK-UP TABLE
`
`MODIFY ADDRESS FIELD
`OF PACKETTONCLUDE
`NEW OUTGONGADDRESS
`
`APPLY SWITCH PORT
`ADDRESS TO PACKET
`
`SEND PACKET TO
`SWITCH FABRIC
`
`UPDATE PARAMETERS
`IN LOOK-UP TABLE
`
`60
`
`62
`
`64
`
`46
`
`50
`
`GUEST TEK EXHIBIT 1008
`Guest Tek v. Nomadix, IPR2019-00211
`
`

`

`U.S. Patent
`
`Apr. 22, 1997
`
`Sheet 1 of 6
`
`5,623,492
`
`RECEIVE PACKET HAVING ADDRESSFIELD
`WHICH IDENTIFIES SOURCE ENDPOINT
`AND DESTINATION ENDPOINT
`
`
`
`
`
`ENFORCE BANDWDTH CONSTRANT
`BASED ON SOURCE DENTIFIED
`N ADDRESS FIELD
`
`ROUTE PACKET BASED ON
`ADDRESS FELD
`
`12
`
`4.
`
`
`
`21
`
`23
`
`
`
`24
`
`PAYLOAD
`
`SOURCE
`
`DESTINATION
`
`17, 2
`
`N-- -
`22
`
`
`
`Cell
`
`PAYLOAD
`
`HEADER
`
`25-
`
`26
`
`77. 27
`
`/ 27
`/
`f
`| 4 bit 8 bit 16 bit 3 bit 1 bit 8 bit
`
`

`

`U.S. Patent
`
`Apr. 22, 1997
`
`Sheet 2 of 6
`
`5,623,492
`
`30-
`
`38
`
`32-2E
`
`PACKET
`PROTOCOL.
`PROCESSOR
`
`FABRIC
`
`
`
`37
`
`PACKET
`PROTOCOL
`PROCESSOR
`
`34 37
`
`plb.
`
`PROCESSOR
`
`PHYSICAL
`NTERFACE
`
`34
`
`36
`
`far, 27
`
`37
`
`34
`
`54
`
`56
`
`PHYSICAL
`INTERFACE
`
`PHYSICAL
`NTERFACE
`
`
`
`3. 6
`
`EXTRACT ADDRESSFIELD
`
`OBTAN BANDWDTH PARAMETERS
`FROM LOOK-UP ABLE BASED
`UPON SOURCE ENDPOINT
`
`36
`
`a
`
`42
`
`
`
`
`
`44
`
`
`
`
`
`PASS
`BANDWIDTH
`PARAMETER
`CONTROLS
`?
`
`YES
`
`NO
`
`46
`
`50
`
`GET NEW OUTGOING ADDRESS
`FIELD AND PHYSICAL SWITCH
`PORT ADDRESS FROM TABLE
`
`DISCARD
`PACKET
`
`UPDATE PARAMETERS
`NOOK-UP TABLE
`
`f 4.
`A.
`
`OF PACKET TO INCLUDE
`NEW OUTGONGADDRESS
`
`APPLY SWITCH PORT
`ADDRESS TO PACKET
`
`SEND PACKET TO
`SWITCH FABRIC
`
`UPDATE PARAMETERS
`N LOOK-UP TABLE
`
`60
`
`62
`
`64
`
`

`

`U.S. Patent
`
`Apr. 22, 1997
`
`Sheet 3 of 6
`
`5,623,492
`
`CONNECTION
`MANAGEMENT
`PROCESSOR
`
`FAST
`PACKET
`SWITCH 1
`
`82b - 82C
`
`86
`
`76
`
`72
`
`80
`
`FAST
`PACKET
`SWITCH2
`
`82d
`
`82a
`
`74
`
`FAST
`PACKET
`SWITCH 3
`
`82g - 82h
`
`84a
`
`84
`
`84C
`
`84d
`
`84e
`
`84f
`
`84g
`
`84h
`
`7, 2
`
`WC - 15 WC1 = 4
`102f
`f02e
`
`
`
`f04
`
`f06C
`
`106b
`
`106a
`
`WP 15
`
`102d
`
`WC = 13
`
`VC = 12
`102C
`
`WP - 15
`
`WP 15
`
`102a
`
`102b
`
`WC = 10 WC = 1
`
`

`

`U.S. Patent
`
`Apr. 22, 1997
`
`Sheet 4 of 6
`
`5,623,492
`
`
`
`n/S users
`
`n/S users
`
`
`
`v
`
`NODE S;
`
`

`

`U.S. Patent
`
`Apr. 22, 1997
`
`Sheet 5 of 6
`
`5,623,492
`
`NODEs
`
`(77. M
`
`1024
`
`
`
`1050
`1000
`950
`900
`850
`800
`750
`700
`650
`600
`550
`500
`450
`400
`350.
`300
`250
`200
`150
`
`OO
`50
`
`4
`
`8
`
`2 16 20 24 28 32 36 40 44 48 52 56 60 64
`Number of Fully InterConnected Users
`
`

`

`U.S. Patent
`
`Apr. 22, 1997
`
`Sheet 6 of 6
`
`5,623,492
`
`727. //
`
`135
`
`142 132
`
`--
`- Y
`
`130
`Napa-
`
`TRAFFIC
`FLOW
`PROCESSOR
`
`FAST
`PACKET
`SWITCHING
`NETWORK
`
`134
`?
`
`136
`
`40
`
`Y
`Y.
`)
`N
`
`140
`
`(727. A
`
`
`
`
`
`150
`
`OBTAN PARAMETER INDICATIVE
`OF BANDWIDTH USAGE ASSOCATED
`WITH END PONT OVER A PLURALTY
`OF VIRTUAL CONNECTIONS
`
`
`
`
`
`
`
`
`
`DOES
`PARAMETER VIOLATE
`APREDETERMINED
`THRESHOLp
`
`FORWARDAT LEAST ONE
`PACKE IN OUEUE
`
`
`
`INHIBITFLOW OF PACKETS
`FORWARDED TO ENDPOINT
`
`UPDATE
`PARAMETER
`
`UPDATE
`PARAMETER
`
`
`
`160
`
`
`
`
`
`
`
`162
`
`154
`
`156
`
`

`

`1.
`METHODS AND SYSTEMS FOR MANAGING
`BANDWDTH RESOURCES IN A FAST
`PACKET SWITCHING NETWORK
`
`5,623,492
`
`TECHHICAL FIELD
`The present invention relates generally to managing band
`width 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.
`
`2
`In accordance with the negotiated traffic contract, the
`connection management processor writes bandwidth param
`eters 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 net
`work 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 shar
`ing bandwidth in the network.
`Disadvantages of the present approach of associating a
`corresponding bandwidth constraint with each virtual con
`nection 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 transmit
`ting 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.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`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 informa
`tion 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. Regard
`less of the type of packet employed, each of the packets is
`further loaded with an address field which contains infor
`mation 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.
`
`SUMMARY OF THE INVENTION
`It is an object of the present invention to reduce band
`width 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 pro
`visioned 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 com
`prises a step of enforcing a bandwidth constraint for the
`plurality of virtual connections based upon a measure of the
`
`45
`
`50
`
`55
`
`60
`
`65
`
`

`

`5,623,492
`
`3
`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 accom
`panying drawings.
`
`4
`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 receiv
`ing 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 asso
`ciating 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 accor
`dance 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 accor
`dance 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.
`
`10
`
`5
`
`25
`
`30
`
`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 man
`20
`agement 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 accor
`dance 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 switch
`ing network.
`
`35
`
`40
`
`45
`
`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 end
`points are bundled together for the purpose of assigning and
`associating bandwidth. Consequently, the cost of imple
`menting 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.
`
`50
`
`55
`
`60
`
`65
`
`

`

`5,623,492
`
`5
`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 indepen
`dent 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 men
`tioned, 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 band
`width 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 transmis
`sion 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 net
`work wherein a plurality of virtual connections are provi
`sioned 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 explic
`itly 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 prede
`termined 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
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`6
`considered as a bundle for the purpose of assigning band
`width 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 rep
`resentative of received and transmitted packets.
`A packet protocol processor 37 performs the packet
`protocol processing. The packet protocol processor 37 pro
`vides means for enforcing a bandwidth constraint based
`upon an address field contained within the received packet.
`Consequently, the line unit 34 enforces a bandwidth con
`straint for packets communicated over a bundle of provi
`sioned virtual connections emanating from a source end
`point 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 accor
`dance 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 embodi
`ments of performing this step are described below.
`
`

`

`5,623,492
`
`10
`
`15
`
`20
`
`25
`
`30
`
`7
`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 desti
`nation 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 contri
`bution 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 rep
`resentative 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 end
`points 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 82?, 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 man
`agement processor 86, which performs functions as earlier
`50
`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
`
`60
`
`8
`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 con
`nections in three bundles, in comparison to having 15
`provisioned virtual connections each having bandwidth
`associated therewith.
`Embodiments of the present invention are further illus
`trated 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 sub
`scriber endpoints. This consists of writing data into all the
`fast packet switches associating addresses and bandwidth
`parameters with all the virtual connections. This is per
`formed 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