Multiplex communications – Pathfinding or routing – Through a circuit switch
Reexamination Certificate
1999-11-12
2003-05-27
Rao, Seema S. (Department: 2666)
Multiplex communications
Pathfinding or routing
Through a circuit switch
C370S395420, C370S415000, C340S870030
Reexamination Certificate
active
06570873
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a packet switch which is used in the Internet communication or the like.
2. Description of the Prior Art
The data traffic in the conventional Internet adopts best effort method and the quality of service (hereinafter, referred to as QoS) of the traffic with respect to a bandwidth, delay, fluctuation, or the like was not considered. That is, when routers and switches (hereinafter, both a router and a switch are referred to as packet switches) receive IP packets to be forwarded, they only forward the packets with QoS which may be provided at each time.
However, with the advents of protocols of RSVP (Reservation Protocol) and DiffServ (Differentiated Service), the QoS of traffic comes to be assured for protocol in the Internet. In addition, a packet switch comes to assure the QoS while classifying traffic by QoS as disclosed in JP 10-200550, A.
Moreover, with the advent of VoIP (Voice over IP), the Internet comes to accommodate telephone voices, and also, there is a trend that telephone service providers establish a conventional PSTN on the Internet. Therefore, the condition which is required to assure QoS in the Internet becomes rigorous.
However, because a conventional packet switch begins the scheduling thereof after a traffic arrives at the switch, it was difficult for the conventional packet switch to realize the QoS which assures the quality of a telephone voice.
When a packet switch forwards a packet, the packet switch must set a switch connection therein in order to transfer the traffic from a certain input port to a certain output port, and in addition, scheduling to arbitrate the contention between switch connections which are set for plural input ports is necessary for the switch.
Referring to
FIG. 6
showing a conventional packet switch, when each of input ports
41
a
and
41
b
receives data addressed to any of output ports
44
a
and
44
b
, each of input ports
41
a
and
41
b
queues the data to queue
45
which is provided for each output port, and outputs a request for a connection with a addressed output port to scheduler
42
in order to request a connection realized in switch
43
. Scheduler
42
looks over the requests for the connections which are received from input ports
41
a
and
41
b
, and allocates each output port to each input port so that connections between input ports
41
a
,
41
b
and output ports
44
a
,
44
b
do not contend with each other. Scheduler
42
sets switch
43
in accordance with the allocations, and outputs GRANT signals for allowing input ports
41
a
and
41
b
to output data to addressed output port
44
a
or
44
b
. Each of input ports
41
a
and
41
b
transmits data which are addressed to the notified destination output port to switch
43
, and switch
43
switches the inputted data to output port
44
a
or
44
b.
The scheduling of the conventional packet switch will be explained with reference to
FIGS. 7
, and
8
. It is assumed that the VOQ (Virtual Output Queue) method is adopted. In accordance with the VOQ method, when an input port receives plural data, the input port is able to simultaneously output plural requests. Each of the plural requests is for a connection with an output port.
Referring to
FIG. 7
, scheduler
42
comprises request matrix generator
52
, scheduling algorithm portion
53
, and allocation matrix processor
54
. Request matrix generator
52
generates a request matrix which represents the status of connection requests by two dimensions, one of which consists of input ports and the other of which consists of output ports, on the basis of requests from input ports. Scheduling algorithm portion
53
performs scheduling on the basis of the request matrix, and generates an allocation matrix which represents the setting of switch
43
by two dimensions, one of which consists of input ports and the other of which consists of output ports. Allocation matrix processor
54
generates a setting signal to be supplied to switch
43
and the GRANT signals to be supplied to input ports
41
a
, and
41
b
on the basis of the allocation matrix.
Referring to
FIG. 8
, request matrix
62
is a two dimensional matrix consisting of input ports and output ports. If a certain input port outputs a request for a connection with a certain output port, the value of the cross point of the input port and the output port becomes one. The example of the request matrix
62
in
FIG. 8
shows that input port
0
is requesting connections with output ports
0
, and
3
, input port
1
is requesting connections with output ports
1
, and
2
, input port
2
is requesting connections with output ports
1
, and
3
, and input port
3
is requesting connections with output ports
0
,
1
, and
2
. Scheduling algorithm
61
performs scheduling on the basis of request matrix
62
. In this case, only a single connection between an input port and an output can be established for each input port and each output port. Therefore, allocation matrix
64
is generated in such a way that a request bit is adopted from the upper leftmost corner to the lower rightmost corner sequentially, and a request bit which is located in a row which already has an adopted request bit or/and in a column which already has the adopted request bit or another adopted request bit will not be adopted. Allocation matrix
64
is a two dimensional matrix consisting of input ports and output ports and if a connection between a certain input port and a certain output port is determined to be adopted, the value of the cross point of the input port and the output port becomes one.
However, it is not possible to schedule a high priority traffic which is required for a telephone voice or the like with a priority when the above scheduling method is used. There is a second method in which scheduling is performed for high priority traffics and the result of the scheduling is adopted with a priority. However, according to the second method, if requests with priorities contend with each other, timing of allocation becomes irregular, thereby causing a fluctuation of a traffic.
SUMMARY OF THE INVENTION
In order to overcome the aforementioned disadvantages, the present invention has been made and accordingly, has an object to provide a system and method for scheduling reservation with priority, which system and method beforehand reserve a scheduling of a switch for a traffic of telephone voice or the like of which priority is high and of which pattern (a pattern as to when a packet belonging to the traffic arrives and as to where the packet is switched) is forecastable by use of connection information (information as to the bandwidth of the traffic, the arrival time of the traffic, the destination of switching of the packet and the like), and thereby enabling to ensure QoS for such a traffic.
That is, the present invention has an object to perform such scheduling that assigns a switch setting with priority to a data traffic of which reception time is forecastable in a packet switch or a cell switch which has a buffer for preventing contentions among packets at the output.
According to an aspect of the present invention, there is provided a system for scheduling a reservation of a traffic with a priority, wherein packets belonging to a high priority traffic are forwarded from an input port to an output port in accordance with the reservation, the system comprising: input ports, each of the input ports comprising: queues which input inputted packets while classifying the inputted packets by addressed output ports and priorities into the queues and output the inputted packets individually when receiving a grant signal; means for obtaining and outputting connection information including a request for reserving a connection of such input port with an addressed output port for packets belonging to the high priority traffic on the basis of signaling of the high priority traffic; and means for outputting a request for a connection of such input port with an addressed output port for a low priority pa
Aramaki Toshiya
Isoyama Kazuhiko
Jagannathan Melanie
NEC Corporation
Rao Seema S.
LandOfFree
System and method for scheduling reservation of traffic with... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for scheduling reservation of traffic with..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for scheduling reservation of traffic with... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3005130