Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-03-11
2003-03-25
Ton, Dang (Department: 2666)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S235000
Reexamination Certificate
active
06539025
ABSTRACT:
FIELD OF THE INVENTION
The present invention is generally related to telecommunications networks, and more particularly to point-to-point and point-to-multipoint arbitration, bandwidth allocation and delay management within an asynchronous transfer mode switch.
BACKGROUND OF THE INVENTION
Telecommunications networks such as asynchronous transfer mode (“ATM”) networks are used for transfer of audio, video and other data. ATM networks deliver data by routing data units such as ATM cells from source to destination through switches. Switches include input/output (“I/O”) ports through which ATM cells are received and transmitted. The appropriate output port for transmission of the cell is determined based on the cell header.
One problem associated with ATM networks is loss of cells. Cells are buffered within each switch before being routed and transmitted from the switch. More particularly, switches typically have buffers at either the inputs or outputs of the switch for temporarily storing cells prior to transmission. As network traffic increases, there is an increasing possibility that buffer space may be inadequate and data lost. If the buffer size is insufficient, cells are lost. Cell loss causes undesirable interruptions in audio and video data transmissions, and may cause more serious damage to other types of data transmissions.
In point-to-point transmission a cell is transmitted from a single input port to a single output port across the switch fabric. In point-to-multipoint transmission a cell is transmitted from a single input to multiple outputs across the switch fabric. In order to execute such a transmission, each of the designated outputs must be available to receive the cell from the transmitting input, i.e., have adequate buffer space. However, the likelihood that each of the designated outputs will be simultaneously prepared to receive the cell when the cell is enqueued decreases as traffic within the switch increases. In some circumstances this may result in delayed transmission. In the worst case, cells will be delayed indefinitely and incoming cells for that connection are discarded. It would therefore be desirable to facilitate transmission by reducing or eliminating delays and cell loss.
SUMMARY OF THE INVENTION
An Asynchronous Transfer Mode (“ATM”) switch and method which facilitate point-to-multipoint and point-to-point transmission is disclosed. The ATM switch includes a bandwidth arbiter, a plurality of input ports including one To Switch Port Processor (“TSPP”) per input port and a plurality of output ports. Each input port within the switch includes a switch allocation table (“SAT”) which grants bandwidth to connections. Each SAT includes a plurality of sequentially ordered cell time slots and a pointer which is directed to one of the slots. The SAT pointers at each input port are synchronized such that, at any given point in time, each of the pointers is directed to the same slot location in the respective SAT with which the pointer is associated. Each TSPP maintains a list of point-to-point connections, and more particularly maintains one such list for each output port in the switch. The bandwidth arbiter maintains a bit vector for each port indicating requested output ports for transmission of point-to-point cells.
Each connection is assigned bandwidth types based on the traffic type associated with the connection. There are two types of bandwidth to grant within the switch: allocated and dynamic. Allocated bandwidth is bandwidth which is “reserved” for use by the connection to which the bandwidth is allocated. Generally, a connection with allocated bandwidth is guaranteed access to the full amount of bandwidth allocated to that connection. As such, traffic types that need deterministic control of delay are assigned allocated bandwidth. Dynamic bandwidth is bandwidth which is “shared” by any of various competing connections. Because dynamic bandwidth is a shared resource, there is generally no guarantee that any particular connection will have access to a particular amount of bandwidth. For this reason dynamic bandwidth is typically assigned to connections with larger delay bounds. Other connections may be assigned a combination of dynamic and allocated bandwidth. Any cell time where the SAT entry is not valid or where the scheduling list does not contain a cell thus represents an unassigned bandwidth opportunity.
To execute point-to-point operation the switch employs the point-to-point request bit vectors and round robin operations to grant dynamic bandwidth to point-to-point connections. At the start of the cell time, matches are determined in parallel for each bit in each selected request bit vector and granting is then executed according to a prioritization scheme begining at a first position. Granting opportunities are then provided to the other request bit vectors until granting opportunities have been provided for each request bit vector. A second position indicates an individual bit which receives priority for the granting opportunity. If bandwdith is not granted, granting opportunities are then provided to the other bits in the request bit vector. In the next cell time the first position is then at the next sequential request bit vector relative to the previous cell time if the output port designated by a second position was granted. Otherwise the first position is unchanged. In this manner each TSPP receives equal treatment over time.
To execute point-to-multipoint operation the bandwidth arbiter maintains a list of connections and bit vectors indicating the designated destination ports for a point-to-multipoint cell. The bandwidth arbiter list is then compared to an unassigned output port bit vector generated from the SATs to determine matches therebetween at which point-to-multipoint transmission may be made by utilizing the instantaneously unused bandwidth within the switch. The bandwidth arbiter may also assign priority to connections in the list.
The bandwidth arbiter may also include a combined arbiter mechanism for allocating dynamic bandwidth for both point-to-multipoint and point-to-point connections. In the preferred embodiment each type of connection, i.e., point-to-multipoint and point-to-point, is prioritized into at least two levels of priority such as HI and LO. Dynamic bandwidth is then granted in four main steps. In a first step dynamic bandwidth is granted to HI priority point-to-multipoint connections in the manner described above. In a second step the dynamic bandwidth remaining from the first step is granted to the HI priority point-to-point connections in the manner described above. In a third step the bandwidth remaining from the second step is granted to the LO priority point-to-multipoint connections. In a fourth step the bandwidth remaining from the third step is granted to the LO priority point-to-point connections.
Switch efficiency is increased by utilizing instantaneously unused bandwidth. When switch traffic increases, available bandwidth decreases. Nevertheless, unutilized bandwidth will be present from time to time, and such bandwidth is wasted if not utilized. Therefore, point-to-point and point-to-multipoint transmissions which would otherwise be dropped are made using the otherwise unutilized bandwidth, and switch efficiency is increased. Such use is made possible by the arbitration techniques which reduce delay.
REFERENCES:
patent: 5051982 (1991-09-01), Brown
patent: 5392280 (1995-02-01), Zheng
patent: 5838681 (1998-11-01), Bonomi et al.
patent: 5956342 (1999-09-01), Manning et al.
Caldara Stephen A.
Colsman Matthias L.
Hauser Stephen A.
Manning Thomas A.
Fujitsu Network Communications, Inc.
Ton Dang
Weingarten Schurgin, Gagnebin & Lebovici LLP
LandOfFree
Priority arbitration for point-to-point and multipoint... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Priority arbitration for point-to-point and multipoint..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Priority arbitration for point-to-point and multipoint... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3036245