Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-05-26
2001-09-25
Rao, Seema S. (Department: 2661)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S412000, C370S428000, C710S053000
Reexamination Certificate
active
06295295
ABSTRACT:
TECHNICAL FIELD
The present invention relates to broadband data communication networks and methods. In particular it relates to the aspect of scheduled transfer of information packets.
BACKGROUND
Martin De Prycker: Asynchronous Transfer Mode, solution for broadband ISDN; ELLIS HORWOOD series in Computer Communication and Networking; 1991, describes a fast information packet switch for switching information, i.e. fixed length information packets or cells, from an inlet logical channel to an outlet logical channel. The switch comprises a central switch core to which several switch ports are connected. The switch ports have two distinct functions: inlet functions and outlet functions, however they are typically implemented in the same hardware. A typical fast information packet switch is an ATM switch where ATM stands for Asynchronous Transfer Mode. The inlet/outlet logical ATM channels is defined firstly, by a physical link or physical inlet/outlet, which is defined by a physical port number, and secondly, by a logical channel on the physical port, i.e. a virtual path, VP, and/or a virtual channel, VC, which are identified by a virtual path identifier VPI and virtual channel identifier VCI respectively. To provide the switching function, both the inlet and the incoming logical channel must be related to the outlet and the outgoing logical channel. This is achieved by using a translation table. Moreover, the problem of when two or more logical channels contend for the same outlet at the same time has to be solved. Hence, three functions have to be implemented in a fast information packet switch: routing, for internally routing the information from an inlet port to an outlet port of the switch; queuing, for buffering cells destined to the same outlet at the same time; and header translation.
Until now there have been four types of ATM traffic: Constant Bit Rate CBR, Variable Bit Rate-Real Time VBR-RT, Variable Bit Rate-Non Real Time VBT-NRT and Unspecified Bit Rate UBR. A fifth traffic type, Available Bit Rate ABR, has recently been defined by the International Telecommunications Union ITU and the ATM-Forum as an ATM service category requiring an interaction between the network and the user. A user should be able to send data, i.e. information packets or cells, at the maximum bit rate allowed by the network at any moment. A flow control protocol for this has been defined. Bit rate or just rate is defined as the number of bits per second bit/s.
It has been a goal that all users shall get a fair share of the available bandwidth in the network at any moment. A weight may be assigned to each user, to determine what share of the available bandwidth the user should have. The weight, and thus the bandwidth, may be the same for all users or may vary. Each switching system in the network must allocate bandwidth to each user according to the relative weight, and serve these users according to this weight.
It is assumed that each inlet port has one logical queue per outlet port. When a cell is to be sent into the core, the queue from which to take this cell must be decided, and also which cell in this queue. In order to achieve fairness, i.e. to give each VP/VC a fair share of the available bandwidth from a queue into the switch core, each queue may be searched, e.g. by means of a scanner, and within each queue each VP/VC. There are, at least, two problems with this. A queue scanner must, for each cell interval, select the next queue that has a cell to send and whose outlet port can accept a cell. When an inlet port has been selected, all incoming VP/VC at this inlet port must be searched sequentially in order to give a fair share of the bandwidth of the selected outlet port to each VP/VC.
If the number of ports is large, and the status of each port is tested sequentially until a port that can send a cell is found, the search may take such a long time that it can not be accomplished within the duration of one cell interval, i.e. within the time it takes to send a cell into the switch core. If, for instance, one port can be tested for each byte of a cell, only 60 ports can be tested. If no cell carrying active information is found during this period, an idle cell must be generated. A parallel or serial/parallel search can be made faster, but requires more hardware. Furthermore, as the number of logical channels could be 4000 or more, it is not feasible to actually search all VP/VCs during one cell time in order to find the next to send.
Furthermore, if one inlet carries 10 VP/VCs destined for an outlet, and another inlet only has one, there is a risk that, at least during some period of time, the single VP/VC gets 50% of the outlet bandwidth and the 10 VP/VCs only 5% each.
An ATM switching system supporting ABR and providing a service for queuing per VC is disclosed in a StrataCom Service Note ABRSN19515M, 1995. So as to furthermore ensure fairness in allocating excess bandwidth said ATM switching system also provides a centralized unit common to all inlet ports for rate scheduling per VC. A centralized unit gives an upper limit on the switch size.
An article by Chao et al.: “Architecture Design of a Generalised Priority Queue manager for ATM Switches”, ISS-95 proposes a switch comprising means for queue scheduling. The proposed switching system has the buffers at the outlet ports for facilitating the scheduling.
U.S. Pat. No. 5,166,930 describes a method and apparatus for giving data devices efficient access to data resources. A plurality of epoch queues are provided at the input so that a limited number of cells from each connection, depending on the weight of the connection, can be sorted into each queue. An overflow queue is used for cells not allowed in the epoch queues. The epoch queues are then emptied cyclically and cells from the overflow queue are sorted into the free epoch queues together with new incoming cells.
In WO 93/07699 a high speed ATM packet switch using memory buffer modules, each serving a group of inlet ports, is disclosed. Each common memory buffer module includes common buffer memory means for storing incoming cells and buffer managing means for managing the cells to be stored. The system further has a space switch means connected to the memory buffer modules and a system scheduler which configures the space switch and co-ordinates the common memory buffer module at every time slot.
In another embodiment, the system also comprises time slot utilization means which controls the use of the future time slots of each input port and output port, a revolving window priority encoder means for determining the earliest common time slot among the future time slots for connection between an input part and one or more output ports, and a list controller which stores the earliest common time slot together with information about the input port and selected output port and configures the space switch at every time slot according to the header of each cell.
P 661 899 A2 describes a system for using the network resources more efficiently and avoiding loss of cells in overload situations. The first and last cell of a frame of cells are given a start-cell and end-cell flag respectively. A packet counter and a send counter are temporarily assigned to a virtual connection. The start-cell and end-cell signals and the packet counter are used to enable the use of the network resources for another virtual connection when no cells are received for the first virtual connection.
U.S. Pat. No. 5,517,495 discloses a method and an input buffered ATM switch for fast local to wide area networks. The switch includes one input buffer for each input port, with one queue for each virtual connection, and a switch fabric and a scheduling control circuit for controlling the processing of the received cells using a fair arbitration round robin (FARR) program. Each input buffer includes a service list associated with each priority level for each output port, and one cell queue for each virtual connection. Each virtual connection has a time stamp, used to match the input buffers with output ports to control
Burns Doane Swecker & Mathis L.L.P.
Rao Seema S.
Telefonaktiebolaget LM Ericsson
LandOfFree
Scheduler for an information packet switch does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Scheduler for an information packet switch, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scheduler for an information packet switch will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2448732