Broadband switching system

[0002] This application is related to copending commonly owned applications:

[0003] U.S. Ser. No. 08/619,653, filed Mar. 22, 1996, now U.S. Pat. No. 5,784,358; U.S. Ser. No. 08/983,268, filed Sep. 10, 1997; U.S. Ser. No. 08/999,749, filed Sep. 10, 1997; and U.S. Ser. No. 09/029,323, filed Feb. 23, 1998.

[0004] 1. Field of the Invention

[0005] This invention relates to a broadband switching system for the switching of asynchronously transferred data cells, and to a method of switching asynchronously transmitted data cells.

[0006] 2. Related Art

[0007] Broadband switching networks for switching asynchronously transferred cells are known, in which a predetermined level of bandwidth is allocated to a transmission channel connecting a first customer to a second customer. In some of these known systems, a communications channel is provided over a significant period of time, effectively of the leased-line type, and manual measures are implemented in order to set up such a connection or to modify a connection according to the particular terminations and the level of traffic being conveyed. Consequently, it is usual for customers to incur a fixed rate charge as part of the overall charge for the connection, resulting in payment being made irrespective as to whether the connection is being used or not.

[0008] Alternative systems have been proposed or are available. In particular, it is possible for connections to be established on a dial-up basis, requiring termination equipment to be provided with facilities for establishing connections by issuing signalling commands and responding to similar commands issued by the network.

[0009] The use of permanent circuits to support a private communications network is widespread. The demand for such circuits is expected to grow to include broadband rates above 2 Mbit/s, the circuits carrying traffic multiplexed from sources which are inherently bursty, possibly together with traffic which is transmitted at constant bit rates and is delay sensitive, such as voice transmission and constant bit-rate video.

[0010] Asynchronous transfer mode (ATM) cells all have a fixed information field of forty eight octets which can carry customer traffic or customer-originating control information (signalling). These two types of data transmission are distinguished by setting virtual path (VP) and vertical circuit (VC) values in the cell headers. Another field provided in the ATM header is known as cell loss priority, which enables low priority cells to be distinguished from high priority cells. In the event of congestion, the low priority cells may be discarded first.

[0011] For private circuits within an ATM based network, the desired route, the required bandwidth, and the quality of service (QOS) are set up using network management procedures. The private circuits are known as permanent virtual circuits (PVCs) because there is no actual physical circuit, only a VP/VC value or “label” which is associated with information stored in the switches to determine the route and preserve the bandwidth and QOS requirements.

[0012] A disadvantage of all known permanent circuits is that the bandwidth remains assigned to the circuit, even when the customer has nothing to transmit. This means that the customer may have to pay higher charges than would be obtained if the bandwidth was only made available when needed. The assumption being made here is that charging is related to reserved bandwidth, and this is not necessarily correct in terms of the way public network operators may choose to charge for virtual circuits. However, it is expected that charging based on reserved bandwidth will become a significant factor in the future.

[0013] A common practice is to set up a permanent virtual circuit so that it is only available during certain hours of the day, or during certain days of the week. A difficulty with this approach is that it does not allow the customer to change the pattern of usage quickly, and it may only crudely reflect the usage required by the customer.

[0014] A second proposal has been to provide the customer with a separate communications channel to the network management plane, thereby allowing a permanent virtual circuit to be reconfigured. A difficulty with this approach is that some time delay will be incurred before the customer can start to use the virtual circuit.

[0015] A third proposal is to introduce equipment at every switching point in the network that recognises a fast resource management cell, indicating that bandwidth should now be assigned to the circuit. A difficulty with this approach is that there is no internationally agreed standard for a bandwidth-requesting cell that would be recognised by the switching equipment produced by the various manufacturers.

[0016] According to one aspect of the invention, a broadband switching system having at least one ingress for connection to a respective signal source and at least one egress for connection to a selected signal receiving system, the switching system having at least one switch for transmitting information-carrying asynchronously transferred data cells from the ingress to the egress, system control means for accepting and establishing a connection between the ingress and the egress via the said switch, and bandwidth control means arranged to detect the cells received at the ingress, and, automatically in response to such cell detection, to cause the system control means to allocate sufficient bandwidth to permit transmission of a predetermined number of cells within a predetermined time period.

[0017] Preferably, the system includes table storing means for a table associating the predetermined time period with the signal source, the time period being a predetermined maximum transmission time for a message comprising a group of the predetermined number of cells, the bandwidth control means having means for recognising the source of the detected cells thereby to identify the maximum transmission time associated with the detected cells.

[0018] In this way it is possible to alter the bandwidth available in the system for cells intended for a given path dynamically, avoiding the need to signal a request for bandwidth prior to being able to transmit cells onto the system and to provide a guaranteed maximum transmission time.

[0019] Preferably, the stored table further includes a message size value, the size value being associated with a respective signal source and being a predetermined maximum number of cells which form a message. Thus, from the stored maximum message size value and maximum transmission time, the system control means is able to calculate the cell rate (and equivalent bandwidth) required to complete the job (transmission of the message) in time. These two items of information typically are pre-registered by a customer.

[0020] The stored table may further include a bandwidth value, the bandwidth value being a predetermined maximum bandwidth allocation associated with a respective signal source.

[0021] Again, this value will typically be pre-registered and will usually correspond to the maximum transmission bandwidth capability of the signal source. This avoids the possibility of a signal source being offered a bandwidth capacity that it cannot fully use which if the system is expecting the bandwidth to be fully used, could result in the predetermined number of cells not being transmitted within the time period and also would result in incomplete use being made of the available bandwidth on the system.

[0022] Optionally, the maximum transmission time may be calculated according to a predetermined finishing time for the transmission of a message to the egress. Thus, a customer may send a message specifying a time by which it must arrive. The system control means and/or the bandwidth controller may be operable to calculate the maximum transmission time based on the current time and the predetermined finishing time.

[0023] Preferably, the system control means is arranged to calculate the bandwidth required to permit transmission of a message in the time period associated with the recognised signal source.

[0024] The bandwidth control means may be arranged periodically to monitor the number of cells of a particular message that have already been sent and to communicate the cell count to the system control means. The system control means may then decide whether the bandwidth allocated to the signal source for the transmission of that message needs to be adjusted to ensure that transmission occurs within the predetermined maximum transmission time.

[0025] It will be appreciated that a signal source may not necessarily make full use of the bandwidth allocated to it and in such a case, it is not sufficient that the system control means allocate sufficient bandwidth for the message to be transmitted in time, it is necessary for the system control means to monitor the progress which has been made in transmitting the message. The counting of cells by the bandwidth controller is one way of doing this.

[0026] The bandwidth controller may be arranged to detect periods of inactivity for a signal source, to measure the length of such inactive periods and to deem cells received at the ingress following a period of inactivity which exceeds a predetermined timeout period, to be the beginning of a new message.

[0027] Preferably, the bandwidth control means are arranged to detect the rate at which cells are supplied to the input port of the system, and bandwidth is requested from the system control means generally on the basis that the transmitting signal source should be allocated as much bandwidth as is available on the system for the indicated route. Such bandwidth will be allocated depending on the level of traffic in the system at the time the system control means is caused to allocate bandwidth. However, in the preferred embodiment of the invention, the rate at which cells are supplied to the ingress from a given signal source is monitored and, if the allocated bandwidth is more than that required to transmit the cells at the monitored rate, the system control means are caused by the bandwidth control means to allocate less bandwidth to these cells, e.g. after a predetermined time interval, thereby making bandwidth available to other customers.

[0028] The bandwidth control means may include feedback means arranged to transmit a maximum output cell rate signal back to the signal source, the indicator signal indicating a cell rate which depends on or matches the allocated bandwidth.

[0029] The bandwidth control means may be arranged also to read a bandwidth-identifying portion of the incoming cells and to cause the system control means to allocate bandwidth to the cells according to the identified bandwidth. The bandwidth control means may also be arranged to limit the rate at which incoming cells are accepted onto the system on the basis of a default bandwidth until allocation of bandwidth by the system control means has occurred. In this situation, buffering is provided in the bandwidth control means to buffer cells whilst bandwidth is being allocated. Such buffering may be used on other occasions when an signal source is transmitting at a higher rate than the rate capable of being accepted by the system at a given time. Indeed, it is preferable for the buffer to have means for detecting when it is filled to a predetermined threshold level, the feedback means being responsive to the buffer to cause a retransmission of a cell rate indicator signal to the signal source when connected to the ingress. Preferably, detection of filling of the buffer to a predetermined threshold level causes a reduced cell rate indicator signal to be transmitted to the signal source, the signal source having the facility then to reduce its cell rate to avoid buffer overflow and consequent loss of data.

[0030] The bandwidth control means of the preferred embodiment are arranged to cause automatic allocation of bandwidth for cells received from a number of signal sources, and may include an activity detector and a controller, the activity detector being operable to detect the incoming cells and to identify the signal source transmitting the detected cells, with the controller being operable in response to the said detection and identification to transmit a bandwidth request message to the system control means to allocate a level of bandwidth specifically to the cells transmitted by that identified signal source.

[0031] The activity detector may include a cell counter for counting cells received from respective signal sources coupled to the bandwidth control means. The cell count so obtained, may be used to generate charging signals for customer billing and other purposes.

[0032] The invention also includes, according to another aspect thereof, a method as claimed in claim 10 of the accompanying claims.

[0033] The invention will now be described in greater detail, by way of example, with reference to the accompanying drawings, in which:

[0034] FIG. 1 is a diagram of a broadband switching system in accordance with the invention;

[0035] FIG. 2 is a diagram of another broadband switching system in accordance with the invention;

[0036] FIG. 3 is a diagram of part of a broadband switching system showing how a single bandwidth controller can be shared by several end-systems;

[0037] FIG. 4 is a block diagram of a bandwidth controller for use in the systems of FIGS. 1 and 2;

[0038] FIG. 5 is a specification description language diagram (SDL) for the activity detector module shown in FIG. 4;

[0039] FIGS. 6-1 and 6-2 are SDLs for the controller module of FIG. 4;

[0040] FIG. 7 is a diagram of a resource management (RM) data cell;

[0041] FIG. 8 is an SDL for the feedback module of FIG. 4;

[0042] FIG. 9 is a diagram of a buffer for the bandwidth controller of FIG. 4;

[0043] FIG. 10 is an SDL for the buffer;

[0044] FIG. 11 is a block diagram of a shaper/multiplexer module and its connection to the buffer of FIG. 6;

[0045] FIGS. 12-1, 12-2, and 12-3 are SDLs for the shaper/multiplexer module.

[0046] In its preferred form, the invention is concerned with a broadband switching network which may form part of or may constitute a public switching network for the transmission of asynchronously transferred data cells between end-systems.

[0047] Referring to FIG. 1, the public network 10 has a plurality of switches operable in asynchronous transfer mode (ATM). In this simple example, the switches include two local switches 12 each having a port for connection to a respective end-system 14, and a transit switch 16 interconnecting the local switches 12. Associated with the switches is a connection admission control function (CAC) 18 and a dynamic bandwidth controller (DBC) 20 for controlling traffic entering the network through one of the local switches 12. This switch 12 also includes a usage parameter control device 22 for dynamically altering the priority of data cells received at the input port 24 of the network from the end-system 14.

[0048] It will be understood that, in practice, the network 10 will include large numbers of local and transit switches 12, 16 and several DBCs 20 all interconnected to form a network having a plurality of ports such as port 24 for connecting several end-systems such as end-system 14. Using the DBC 20, the public network 10 is able to provide an available bit rate (ABR) service, the DBC acting to detect incoming cells supplied to the input port 24 and, automatically in response to this detection, to cause the CAC 18 to allocate sufficient bandwidth for the transmission of the cells to the destination end-system within a predetermined time period. Generally, end-systems 14 requiring the ABR service are allocated to a fixed DBC 20. There may be more than one DBC 20 for each local ATM switch 12. In the case of a fault, end-systems can be rerouted to a standby DBC (not shown).

[0049] Data is transmitted in the form of asynchronous transfer mode (ATM) cells, each having an information field of forty-eight octets, in addition to a header of five octets, which includes information facilitating transmission through the network itself. Thus, routing is controlled on a cell-by-cell basis and a plurality of transmission paths and time multiplexed slots may be employed for any particular link. ATM cells are, therefore, transmitted via virtual paths and virtual circuits, as defined by the header information.

[0050] The virtual paths and virtual circuits are identified by a virtual path identifier (VPI) and a virtual channel identifier (VCI) in the five octet header which effectively defines the connection between the end-systems so that cells forming part of a common message will be transmitted over the same connection. ABR traffic enters the public system 10 by routing cells according to their VPIs and VCIs through the DBC 20 and then out to external routes, as shown in FIG. 1. From the DBC 20, the traffic on each virtual path and virtual channel is restricted to a cell rate (which will be referred to hereinafter as “CR”), determined by the CAC 18.

[0051] An alternative illustrative arrangement is shown in FIG. 2. In this case, end-system 14A is subject to the control of more than one DBC. In fact, the connection between two end-systems 14A, 14B is routed through two public networks 10-1 and 10-2. Each network 10-1, 10-2 has its own DBC 20-1, 20-2 responsible for restricting traffic entering the network according to the bandwidth allocated by its own connection admission control function (CAC) 18-1, 18-2. Each DBC 20-1, 20-2 is also responsible for advising the end-system 14A of the current applicable CR.

[0052] In the systems of both FIG. 1 and FIG. 2, a customer pre-registers the maximum transmission rate of their end-system, the maximum time for the transmission of a file and optionally the maximum file size that they wish to send. A customer may alternatively register a predetermined time of arrival.

[0053] The customer is not bound to send this file size nor at the maximum transmission rate and may send a smaller file than the maximum size and/or at a slower rate than the maximum rate. The CAC 18, 18-1, 18-2 then allocates bandwidth to the cells which is sufficient to permit the file to be transferred within the maximum transmission time. This allocation is then indicated to the DBC 20, 20-1, 20-2 which communicates the CR to the transmitting end-system 14.

[0054] It is possible for a single dynamic bandwidth controller (DBC) to be shared by several end-systems or signal sources. For example, referring to FIG. 3, a DBC 20-3 is shown connected to a broadband ATM switch 12-3 forming part of the network 10, the traffic of three sources 14C being handled using an output buffer 28. The number of sources which can be handled by the DBC 20-3 is determined by the link rate L (i.e. there must be not so many sources that it is always the link rate L which is the limiting factor determining the available rate.) The aggregate cell rate of the ABR traffic from the sources 14C must not exceed L. This implies that if the traffic from each source is bursty, there may be times when the output buffer 28 is congested. This can be avoided by supplementing the cell rate (CR) feedback to the end-systems 14C with generic flow control (GFC) signals which operate to stop all transmissions from each source immediately.

[0055] Whenever the dynamic bandwidth controller (DBC) is incorporated in the arrangements of FIGS. 1, 2, or 3, its main functions are as follows.

[0056] Firstly, it provides buffering of incoming data cells, the degree of buffering at any given time being determined according to the transmission containing the cells, the transmission being identified by the VPI and VCI information referred to above. The DBC further controls or “shapes” the traffic fed to the network 10 so as to be equal to the current CR applicable to that particular transmission, the CR depending on the allocated bandwidth.

[0057] The allocated bandwidth, and hence the CR, for any given transmission is determined by the CAC 18 (see FIG. 1) on the basis of determining the route to be followed by the transmission and assigning a fair share of the available capacity on the route based upon the known number of active transmissions and based upon the need to finish a job within a predetermined maximum time.

[0058] When a transmission begins it is detected in the DBC, which immediately transmits a low default CR to the relevant end-system 14 (see FIG. 1). Thus a connection is always allowed but it should be noted that the low default CR may have a value of zero. The reduction to the low default CR ensures that a newly active transmitting source does not cause overload in the system 10 before the CAC 18 has been able to allocate bandwidth and derive a CR for that transmission. Such overload would typically cause cell loss for that transmission. The traffic associated with that transmission leaving the DBC 20 is shaped to correspond to the default CR. This is part of a second main function of the DBC, i.e. to send a feedback signal to the end-system for the purpose of controlling its transmitted cell rate. Indeed, each time the CAC 18 derives a new CR for a transmission, a CR advice signal is fed back to the end-system.

[0059] The pre-transmission buffering of the DBC is used to allow a cooperating end-system sufficient time to adjust its output to the latest CR feedback advice. This implies that there is sufficient buffering in the DBC to allow excess cells to enter for a period at least equal to the round trip delay between the DBC and the end-system. If cells continue to arrive from the end-system 14 at a rate greater than the advised feedback CR (for instance, because the CR was lost en route, or because of a faulty end-system) the excess cells will be dropped in the DBC by overflow of the buffer.

[0060] In the preferred DBC, it is also possible to include fault tolerance by making use of a buffer threshold. When the stored cells relating to a given transmission reach the threshold, retransmission of the CR advice feedback to the end-system is triggered. This feature is useful also as a mechanism for policing end-systems to prevent inefficient use of bandwidth, whether due to a faulty terminal or due to deliberate non-compliance with contracted transmission rules. In this way, interference with the quality of service provided for other, compliant end-systems is prevented. In effect, the DBC defines the ABR traffic contract with the network 10.

[0061] The modules of the DBC 20 will now be described in more detail with reference to FIG. 4.

[0062] The DBC 20 is shown in FIG. 4 is a discrete unit having an input port 30 for receiving asynchronously transmitted data cells, an output for feeding data cells onto a switch 12 or 16 (see FIGS. 1 and 2) forming part of the switching network 10. The unit also has another input 34 for receiving messages back from the switch 12 or 16 and a feedback output 35 for transmitting feedback messages to the end-system 14 (shown in FIG. 1). Although the DBC 20 is shown as a discrete unit, it will be appreciated that FIG. 4 can be regarded as a functional diagram representing a subset system of a larger data processing unit, much of which may be embodied as software functions.

[0063] Incoming cells on input 30 arrive as a user cell stream which is fed firstly to an activity detector 36. The purpose of the activity detector is to provide state information to a controller module 38 about each received transmission, each transmission being identified by its VPI and VCI contained in the cell headers. A transmission is labelled active by the activity detector 36 if it was previously quiet and a cell having the appropriate VPI and VCI values is observed to be transmitted from an end-system to input 30. Synchronisation of the activity detector 36 with the start of a cell header may be carried out using an error check field contained in the cell header. The error check field, provides a degree of redundancy, by which error checking may be performed on the header information. Thus, the principal reason for providing the header error check field is to ensure that the header information is correct, thereby ensuring that cells are not transmitted to erroneous addresses.

[0064] A transmission is considered to be in an inactive state if it was previously active and no cell having the appropriate VPI and VCI has been detected for a period of time t.

[0065] Activity detector 36 maintains a timer and state table for each VPI/VCI value pair. Preferably, t is set to be several seconds so that active-inactive-active transitions relating to any given VPI/VCI value pair which are of the order of several milliseconds remain undetected so that the transmission is indicated as remaining in the active state under these conditions. This has the effect of reducing the frequency of messages sent by the DBC 20 to the CAC 18 at some expense to lowering utilisation of the network.

[0066] Another function of the activity detector 36 is that of counting the cells for transmission during an interval after receiving a “start cell count” request from the controller 38. This information can be used, for example, for charging purposes and also by the controller 38 for assessing the actual cell rate of received transmissions.

[0067] Pseudocode for the activity detector is listed below and the corresponding SDL appears in FIG. 5.

[0068] BEGIN {cell arrival}

[0069] cell arrival from end-system

[0070] read VC

[0071] reset VC inactivity timer

[0072] IF VC is newly active THEN

[0073] update state table

[0074] advise CONTROLLER of newly active VC

[0075] ELSE IF counting.cells(VPI/VCI) THEN

[0076] increment cell.count(VPI/VCI)

[0077] ELSE

[0078] do nothing

[0079] END

[0080] BEGIN {VC timer expires}

[0081] VC inactivity timer expires indicating quiet VC

[0082] update state table

[0083] advise CONTROLLER of quiet VC

[0084] counting.cells:=FALSE

[0085] END

[0086] BEGIN {receive a start.cell.count signal}

[0087] receive a start.cell.count(VPI/VCI) signal from CONTROLLER

[0088] cell.count(VPI/VCI):=0

[0089] counting.cells:=TRUE

[0090] END

[0091] BEGIN {cell.count timer expires}

[0092] cell.count timer expires

[0093] send cell.count(VPI/VCI) to CONTROLLER

[0094] restart cell.count timer

[0095] END

[0096] It will be seen that, as far as the incoming user cell stream is concerned, the activity detector 36 reads the VPI/VCI values in each cell header of the arriving cell stream, and this information is used to update the state table which it maintains for each VPI/VCI value pair. As far as communication with the controller 38 is concerned, the detector 36 informs the controller of a change of state of any VPI/VCI value pair. The controller can inform the activity detector of the timer value t to be used.

[0097] Preferably, the same value of t is used for all VPI/VCI value pairs. Cell count information is sent to the controller 38 by the activity detector 36 at the end of each timer expiry. The cell count may be passed on to the CAC 18 by the controller 38 as described below, in order to determine how much of a job has been transmitted so far.

[0098] The cells of the user cell stream arriving on input 30 are transmitted without delay to a buffer module 40 where they are stored in first-in, first-out (FIFO) buffer queues, each queue comprising cells having a given VPI/VCI value pair. The detector 36 is non-specific to cell type. Thus, the arrival of any data cells will be detected and can potentially affect the activity state associated with a VPI/VCI value pair, independently of the existence or absence of control or management cells. Buffered cells are fed from the buffer 40 to a shaper multiplexer module 42 prior to being fed to an ATM switch via output 32. Operation of the buffer and shaper/multiplexer modules 40, 42 will be described in more detail below. For the time being, it is sufficient simply to say that the buffer module is capable of signalling to the controller 38 when any buffer queue has reached a predetermined buffer fill threshold. The shaper multiplexer module 42 is responsible for removing cells from the buffer module 40 and transmitting them onwards towards their destination. It includes a multiplexer function and the shaper stores a CR value for each VPI/VCI value pair so that the cell stream fed from the output is shaped to ensure that the capacity of the respective path through the network for each transmission, as determined by the allocated bandwidth, is not exceeded. The controller 38 also controls a feedback module 44 for receiving feedback messages from the network on input 34 and from the controller 38 itself, for onward transmission to the end-system 14 via output 35. The functions of the buffer, shaper/multiplexer, and feedback modules 40, 42 and 44 will be described in more detail below. The controller 38 will be considered first.

[0099] The purpose of the controller 38 is to signal to the CAC 18 that an ABR type transmission identified by any given VPI/VCI value pair should have bandwidth in the system allocated or re-negotiated. In this embodiment, the controller transmits a bandwidth re-negotiation signal to the CAC 18 which is recognised by the CAC 18 as a signal in respect of a transmission which must be completed within the preregistered maximum time. The CAC therefore advises the controller of a bandwidth which will achieve this (the CAC bandwidth allocation strategy is described below).

[0100] The new CR is sent via feedback, to the end-system and is also sent to the shaper module 42. The controller 38 instructs the activity detector 36 to perform a count of cells received and periodically, the controller 38 sends a cell count signal based on the cell count produced by the activity detector 36 to the CAC 18.

[0101] The controller 38 is also responsible for monitoring the actual sending rate of users in cases of transmissions having seized a large effective capacity. This is done by initializing a timer in the activity detector 36 which may have a time-out period of a few seconds, and at the end of this period the activity detector delivers a cell count to the controller 38. This information is processed to estimate the system capacity equivalent to the actual sending rate of the user. If this capacity is substantially less than the currently allocated capacity, it may imply that the user is attempting to keep a large capacity simply by sending a relatively slow trickle of cells to input 30 to keep the activity detector status for the relevant transmission in the active state. Clearly this situation results in inefficient use of the network, and the following steps are performed by the controller 38 when there is a substantial mismatch in the capacity assigned and currently used. Firstly, the shaper 42 is immediately re-set to drop to the actual CR for the relevant VPI/VCI value pair. Next, the feedback module 44 is commanded to issue the actual CR to the user via output 35. Finally, the controller 38 sends a bandwidth re-negotiation signal to the CAC, the signal including a bandwidth value which is set equal to the current equivalent capacity being used by the user. This signal is then interpreted by the CAC as an option to free capacity for other customers. As an alternative, the mismatch may be dealt with by assigning to the shaper and the feedback modules 42, 44 a default CR rather than the actual CR.

[0102] As mentioned above, the controller 38 is also arranged to receive a signal from the buffer module 40 when the buffer fill for a given VPI/VCI value pair has reached a given threshold. This signal causes the controller 38 to command the feedback module 44 to issue a so-called resource management (RM) cell, which will be described in more detail hereinafter. The controller 38 may also receive a DBC identity value for each new transmission (identified by a new VPI/VCI value pair) which is established, this DBC identity value being received from the CAC. Alternatively, the DBC may use a default identity if none is supplied.

[0103] Pseudocode for the controller appears below:

[0104] BEGIN {receive an active VPI/VCI from ACTIVITY DETECTOR}

[0105] receive active (VPI/VCI) from ACTIVITY DETECTOR

[0106] send minimum CR to feedback

[0107] send minimum CR to shaper

[0108] send bandwidth request (VPI/VCI) to CAC

[0109] send start.cell.count to ACTIVITY DETECTOR

[0110] END

[0111] BEGIN {receive a cell.count from AD}

[0112] receive a cell.count from ACTIVITY DETECTOR

[0113] send cell.count to CAC

[0114] END

[0115] BEGIN {receive a VPI/VCI buffer threshold signal}

[0116] receive a VPI/VCI buffer threshold signal

[0117] signal feedback to retrausmit CR to end-system

[0118] END

[0119] BEGIN {receive a CR from CAC}

[0120] receive a CR from CAC

[0121] send CR to shaper

[0122] send CR to feedback

[0123] END

[0124] BEGIN {receive an inactive signal}

[0125] receive an inactive signal

[0126] advise CAC of inactive VPI/VCI

[0127] END

[0128] SDLs for the controller are shown in FIGS. 6-1 and 6-2.

[0129] The controller 38 is arranged to write a DBC, VPI/VCI identity value pair into the feedback module 44. It is also arranged to instruct the feedback module 44 to issue a resource management command for a specific VPI/VCI value pair. This instruction may also contain an appropriate CR pair T, τ, (T is an average cell inter-arrival time and τ is a burst tolerance). It should be noted that only one change in the values specified in an RM cell is sent for each new VPI/VCI value pair whenever the CAC updates the CR value. Typically, this may be once every 30 seconds or more in a public network, and depends upon the sensitivity setting of the activity detector in the DEC 20. It follows that the required feedback control bandwidth can be relatively small.

[0130] As will be seen from the pseudocode, the controller 38 receives signals from the buffer module 40 whenever a buffer fill threshold is reached by cells having a specific VPI/VCI value pair.

[0131] The interface with the activity detector 36 has already been described.

[0132] The purpose of the feedback module 44 will now be described briefly.

[0133] As mentioned above, the feedback module 44 transmits current CR values (as signalled by the controller 38) to the end-system via output 35. The CR is transmitted using a resource management cell as shown in FIG. 7. Optionally, one field of this cell is the DBC identity value which is used to enable an end-system 14 (see FIG. 1) to distinguish between CR advices from different DBCs (e.g. DBCs 20-1 and 20-2 as shown in FIG. 2) in the end-system to end-system path. This DBC identity field is indicated as field 50 in FIG. 7. The CR is placed in field 52. This RM cell, like other cells, has a five octet header which contains a PT field 54 indicating that the cell is a resource management (RM) cell.

[0134] It is proposed that, if used, DBC identity values are not fixed but are chosen at the time of setting up the transmission path through the network for a given a VPI/VCI value pair. This implies that the CAC 18 assigns a value for the DBC identity for each VPI/VCI value pair, and the feedback module 44 maintains a table of (DBC, VPI/VCI) identity pairs. For example, in FIG. 2, public network 10-1 is arranged to choose a DBC identity for a given VPI/VCI pair and signals this information forwards so that public network 10-2 does not chose the same value (e.g. public network 10-1 assigns identity 1, public network 10-2 assigns identity 2, etc). The DBC identity value is stored in a table maintained by the feedback module 44.

[0135] The CR field 52 in the RM cell (see FIG. 7) contains the CR advice from the CAC which is provided as the average cell inter-arrival time T, plus a burst tolerance i.

[0136] Operation of the feedback module 44 is triggered by the controller 38 (a) when a new CR is advised by the CAC 18, and (b) when the buffer fill level in buffer module 40 corresponding to any VPI/VCI value pair rises above the buffer fill threshold. A resource management (RM) cell is then sent to the end-system.

[0137] The pseudocode for the feedback module 44 is as follows and the corresponding SDL is shown in FIG. 8.

[0138] BEGIN {Receive a CR}

[0139] receive a CR for a VPI/VCI from Controller

[0140] default_CR:=CR

[0141] END {Receive an CR}

[0142] BEGIN {RM.cell timer expires}

[0143] RM.cell timer expires

[0144] create RM.cell

[0145] write default.CR into RM.ceil

[0146] send RM.cell to end-system

[0147] restart RM.cell timer

[0148] END {cell arrival from network}

[0149] Next the buffer module 40 will be considered.

[0150] The buffer module is shown in more detail in FIG. 9. Its purpose is to store incoming data cells on the basis of the VPI/VCI value pairs contained in the cells. Buffering the cells allows an end-system 14 (FIG. 1) time to respond to a feedback signal from module 44. Another function of the buffer module 40 is to send a signal to the controller 38 when the buffer fill threshold is reached, indicating that an end-system is not responding to a feedback signal (this in turn causes the controller 38 to re-send a cell rate signal (CR) to the end-system, as mentioned above). The buffer module 40 also drops received cells when the maximum buffer allocation for a given VPI/VCI value pair is exceeded. This is done by buffer overflow.

[0151] The size of buffer required for a DBC 20 controlling access to the switching system 10 could be relatively small. For example, if the DBC 20 has a combined input rate from all sources of 150 Mbit/s, then, if the round trip delay to the end-system is 100 μs, there will be less than 35 cells in flight whenever the CR values are changed.

[0152] The size of the shared memory area 56 is mainly to cater for changes in the burst tolerance, because a change in this rate leads to only a small number of excess cell arrivals (e.g. around 35 cells). The fixed cell positions assigned to respective VPI/VCI value pairs are designated by the reference numeral 58 in FIG. 9. The cells in these positions represent the front cells of a plurality of queues, each queue having its own VPI/VCI value pair. In other words, the queues can be visualised as running horizontally in FIG. 9 with the front cells at the right hand side. Cells arriving in the buffer module 40 are placed in the queues in a first-in, first-out (FIFO) order.

[0153] Cells are removed from the buffer module 40 when an appropriate signal is received from the shaper section of the shaper/multiplexer module 42, as defined by the buffer module pseudocode which follows:

[0154] BEGIN {Receive a cell}

[0155] receive a cell

[0156] put cell in buffer

[0157] IF buffer-fill level=Threshold THEN

[0158] transmit buffer-fulll signal to CONTROLLER

[0159] ELSE

[0160] do nothing

[0161] END {Receive a cell}

[0162] BEGIN {Receive a fetch}

[0163] receive a VPI/VCI fetch signal from the SHAPER/MUX

[0164] pass cell from buffer to the SHAPER/MUX

[0165] decrement buffer-fill level

[0166] END {Receive a fetch}

[0167] The corresponding SDL appears in FIG. 10.

[0168] Referring now to FIG. 4 in combination with FIG. 11, the shaper/multiplexer module 42 operates to remove cells from the buffer module 40 and to transmit them onwards towards their destination via the network switches. Module 42 has two parts which are a multiplexer 60 and a shaper 62. For each VPI/VCI value pair, the shaper 62 maintains a cell rate (CR) value and a timer.

[0169] The cell stream fed to output 32 is shaped by the shaper so that bursts which are not greater than the burst tolerance τ pass without being delayed by the shaper 62. However, the multiplex function may delay a cell if several transmissions represented by different VPI/VCI value pairs are bursting simultaneously. In this case, the multiplexer 60 assigns each active VPI/VCI value pair a fair share of the DBC output bandwidth. It does this by polling active VPI/VCI value pairs in a round-robin fashion. Cells which are waiting for a period equal to or greater than the rate interval T are flagged with a higher priority “cell must go” value. The multiplexer picks up these cells first (see FIG. 11). Cells will be forced to wait by the shaper function if bursts arrive which are longer than the burst tolerance credit value. The detailed operation of the shaper/multiplexer module 42 will become apparent from the following pseudocode:

[0170] 1. BEGIN {STATE=ACTIVE}

[0171] receive a cell.waiting[VPI/VCI] signal from buffer

[0172] IF burst credit ok THEN

[0173] cell.can.go:=TRUE

[0174] STATE:=WAIT for multiplexer

[0175] ELSE {burst credit not ok}

[0176] STATE:=WAIT for credit timer to expire

[0177] END

[0178] 2. BEGIN {STATE=WAIT for credit timer to expire}

[0179] credit timer expires

[0180] increment burst tolerance credit counter

[0181] cell.can.go:=TRUE

[0182] cell.must.go:=TRUE

[0183] STATE:=WAIT for multiplexer

[0184] END

[0185] 3. BEGIN {STATE=WAIT for multiplexer}

[0186] receive a fetch.cell[VPI/VCI] from multiplexer

[0187] decrement credit counter

[0188] cell.can.go:=FALSE

[0189] cell.must.go:=FALSE

[0190] STATE:=ACTIVE

[0191] END

[0192] 4. BEGIN {STATE=WAIT for multiplexer}

[0193] credit timer expires

[0194] IF credit counter<τ THEN

[0195] increment credit counter

[0196] ELSE

[0197] do nothing

[0198] cell.must.go:=TRUE

[0199] END

[0200] 5. BEGIN {STATE=SHAPER ACTIVE}

[0201] credit timer expires

[0202] IF credit counter<τ THEN

[0203] increment credit counter

[0204] ELSE

[0205] do nothing

[0206] cell. must.go:=TRUE

[0207] END

[0208] 6. BEGIN {STATE=SHAPER.CR ACTIVE}

[0209] new CR advised (T, τ)

[0210] nextT:=T

[0211] nextcredit:=τ

[0212] END

[0213] 7. BEGIN {STATE=SHAPER TIMER ACTIVE}

[0214] timer expires

[0215] reset timer (nexT)

[0216] END

[0217] 8. BEGIN {STATE=MULTIPLEXER ACTIVE}

[0218] output cell timer expires

[0219] index:=pointer

[0220] REPEAT {1st loop of searching for cell.must.go}

[0221] increment index

[0222] IF cell.must.go[index] THEN

[0223] pointer:=index

[0224] fetch cell[index] from buffer

[0225] send fetch cell signal to SHAPER

[0226] STATE:=MUX.ACTIVE

[0227] ELSE

[0228] IF index=max.buffer.size THEN

[0229] index:=0

[0230] UNTIL index=pointer

[0231] REPEAT {2nd loop of searching for cell.can.go}

[0232] increment index

[0233] IF cell.can.go[index] THEN

[0234] pointer:=index

[0235] fetch cell[index] from buffer

[0236] send fetch cell signal to SHAPER

[0237] STATE:=MUX.ACTIVE

[0238] ELSE

[0239] IF index=max.buffer.size THEN

[0240] index:=0

[0241] UNTIL index=pointer

[0242] send no.cell.waiting.signal

[0243] END

[0244] When the CAC 18 receives a bandwidth request from the controller 38, it must first determine whether sufficient bandwidth is available to allow the file to be sent within the pre-registered maximum time. If sufficient bandwidth is not available, bandwidth is “robbed” from other users as described below. Confirmation of allocated bandwidth is then sent to the controller 38 which forwards the bandwidth allocation to the end-system via the feedback module 44.

[0245] The CAC 18 periodically receives a cell count signal (as described above) from the controller 38 which is used by the CAC 18 to monitor how much of the transmission has been sent (and how much is still to be sent). The bandwidth which will be required to allow the transmission to be sent in time can then be reassessed in the light of the cell count. It will be understood that even though sufficient bandwidth is given to the end-system the end-system may “fall behind” if it does not use all of the bandwidth allocated to it. In this case, the CAC 18 will offer a greater bandwidth to allow the end-system to “catch up”.

[0246] The CAC 18 also stores information relating to the maximum transmission rate of the end-system. Thus, the CAC 18 will not allocate more bandwidth than the end-system is able to use. Once the CAC 18 has calculated that the maximum bandwidth must be allocated to an end-system until the end of the job, that bandwidth is tagged as “do not rob” to prevent bandwidth being removed which would make it impossible to meet the maximum transmission time deadline.

[0247] It will be understood that when the DBC 20 requests a change in the bandwidth allocated to a particular transmission, the CAC must control other traffic in the network so that the network capacity is used most effectively. The description which follows deals with connection admission control methods for overcoming the problem of traffic rebalancing.

[0248] Two connection admission control strategies will now be described. Both tackle the problem of rebalancing traffic. In other words, when a transmission becomes quiet or newly active, it is necessary to determine how many other control messages need to be generated for other transmissions. The object is to make this number of control messages as small as possible.

[0249] The first strategy involves a relatively simple connection admission control method which involves no actual rebalancing. In this method, a newly active transmission (VPI/VCI value pair) is given a single sustained cell rate (CR) which is retained until the transmission goes quiet again. Only when it is subsequently reactivated will the transmission get a different CR. This means that a quiet signal relating to one VPI/VCI value pair will cause no control signals to be generated for other VPI/VCI value pairs which were sharing capacity with it.

[0250] This is combined with a filling method which involves (i) giving a first newly active connection an effective capacity which is half of the total available capacity; (ii) giving the next newly active connection an effective capacity which is half of the remaining capacity; (iii) giving the next newly active connection an effective capacity which is half of the still remaining capacity; and so on. This method is applied link-by-link over the entire route identified by the VPI/VCI value pair, and whichever yields the lowest effective capacity is the determinant of the CR fed back to the DBC 20.

[0251] It follows that a newly active signal having one VPI/VCI value pair generates no control signals for the other VPI/VCI value pairs which are sharing the capacity.

[0252] Since the DBC 20 is designed such that a user can only maintain a large effective capacity on the network so long as the VPI/VCI value pair remains in the active state in the activity detector 36 (FIG. 4), and the cell rate generated by the customer is close to the effective bandwidth value (refer to the cell-counting function of the activity detector described above), it follows that users can only hold onto large effective bandwidths for as long as they are prepared to be charged for the proportionally larger loads which they are submitting.

[0253] This method is fair to users in the sense that, over a sufficiently long period, no user is systematically given a poorer capacity.

[0254] However, it is desirable in some circumstances to increase the number of users who are able to secure relatively large bandwidth allocations and this can be catered for by a second, modified method as follows.

[0255] In this case the underlying principle is that, if an active signal causes control signals for other VPI/VCI value pairs, let the signal be limited to only one per link, namely the richest (largest capacity) VPI/VCI value pair. This can be described as a limited rebalancing method or a “take-only-from-the-richest” (Robin Hood) method.

[0256] This can best be illustrated with an example filling method:

[0257] (i) the first newly active VPI/VCI value pair is assigned an effective capacity equal to half of the total available capacity;

[0258] (ii) the next newly active connection is assigned half of the remaining capacity plus a fifth of the effective capacity of the first VPI/VCI value pair (i.e. the current richest);

[0259] (iii) the next newly active connection is assigned half of the remaining capacity plus one fifth from the current richest; and so on.

[0260] To illustrate this process, it may be imagined that there is a single link with a capacity of 100 Mbit/s. The above steps then result in the following exemplary steps:

[0261] (i) the first newly active VPI/VCI value pair gets 50 Mbit/s and there is 50 Mbit/s remaining;

[0262] (ii) the next VPI/VCI value pair gets half of the remainder (which yields 25 Mbit/s) plus a fifth from the first, which means that the first now has 40 Mbit/s, and the second has 35 Mbit/s;

[0263] (iii) the next VPI/VCI value pair gets half of the remainder, which yields 12.5 Mbit/s plus a fifth from the first, so that the first now has 32 Mbit/s, the second still has 35 Mbit/s, the third has 20.5 Mbit/s, and so on.

[0264] Note that more of the users are now getting large capacities, but there is only one extra control message to send on the link. There is thus a limited rebalancing or “Robin Hood” strategy.

[0265] To extend the method to a route with many links, the above process is repeated link-by-link. Whichever link yields the lowest effective capacity is the determinant of the CR value sent back to the DBC. Now, using this value of effective capacity, the CAC assigns it link-by-link by taking half of the remaining capacity on that link, and any extra which is needed is taken from the richest VPI/VCI value pair on that link. Consequently, this generates at most one additional CR control message per link for each VPI/VCI active signal sent to the network. A quiet signal still generates no additional control messages.

[0266] This strategy also makes it impossible for a user to hold onto a very large capacity when others become active. In addition, as many users as possible are given a reasonably large capacity while keeping the complexity of traffic rebalancing to a minimum.

[0267] In summary, there is provided a broadband switching system for the switching of asynchronously transferred cells of data, a dynamic bandwidth controller (DBC) controls the application of data cells to an input port of the system, the data cells being supplied by a number of transmitting end-systems.

[0268] When an end-system begins transmitting data cells, the DBC detects the presence of incoming cells and requests bandwidth from a CAC forming part of the system.

[0269] The switching system stores a table associating a number of signal sources connected to the input port with respective predetermined maximum transmission times and maximum transmission rates for the sources. When arrival of cells at the input port from one of the source is detected, the DBC and CAC operate together to allocate sufficient bandwidth in the switching system to allow the respective message size to be transmitted within the respective maximum transmission time. A guaranteed minimum rate of transmission is also guaranteed for the source.