EP1049352A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Shakeup technique to improve scheduling techniques for input-queued switches
Assignee: NEC Corp
•
Filing: 1999-11-17
•
Granted: —
•
Expires: 2019-11-17
Abstract
Abstract A scheduling method in a switch is disclosed, the switch including input ports (25.11-25.14) and output ports (25.5-25.54), each input port having one queue each for each said output port, thereby each input port having as many queues as a number of said output ports. Each input ports is represented as a node in a first set of vertices of a bipartite graph (23.1) and each said output ports is represented as a node in a second set of vertices of said bipartite graph (23.2). Each non-empty queue between any of said input ports and any of said output pods is represented as an edge between a vertex in said first set corresponding to said any of said input ports and a vertex in said second set corresponding to said any of said output ports, thereby creating a set of edges (23.3). An initial matching is performed by finding a subset of edges such that no vertex is incident to more than one edge in said subset (23.4). An unweighted shakeup matching for a hitherto unmatched vertex x in said first set to a vertex y in the second set is performed by performing an appropriate one of the following two steps, wherein if x matches with more than one of said vertices in the second set, vertex y being selected at random: adding new matching (x,y) if y is not part of any previous matching (23.9); replacing a matching involving y by a matching (x,y) if y is already part of a matching (z,y) wherein z is a vertex in said first set (23.11). A weighted shakeup method also considers the length of each queue.
Inventors
- 👤 Mark c/o NEC U.S.A. Inc. Goudreau
- 👤 Stavros c/o NEC Research Inst. Inc. Kolliopoulos
- 👤 Satishi c/o NEC Research Inst. Inc. Rao
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-24 16:37
CPC Classifications
H; H04; H04L; H04L49/00; H04L49/30; H04L49/3081; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L47/00; H04L47/50; H04Q; H04Q11/00; H04Q11/04; H04L2012/5678; H04L2012/5679; H04Q2213/00; H04Q2213/1305; H04Q2213/13093; H04Q2213/131; H04Q2213/13103
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
264 words
A computer-implemented unweighted queuing
method for a system with M groups of N input queues each
of said N input queues requesting a unique one of N services,
wherein M and N are natural numbers, characterized by the
steps of: a)(23.1) representing each of said M group as
a node in a first set of vertices of a bipadite graph; b)(23.2) representing each of said N services
as a node in a second set of vertices of said bipartite
graph; c)(23.3) representing each non-empty queue as
an edge between a vertex in said first set corresponding
to one of said M groups to which said each non-empty queue
belongs to and a vertex in said second set corresponding
to a service requested by said each non-empty queue; d)(23.4) performing an initial matching by
finding a subset of edges such that no vertex is incident
to more than one edge in such subset; e) (23.6-23.11) performing an unweighted
shakeup matching for a hitherto unmatched vertex x in said
first set to a vertex y in the second set by performing
an appropriate one of following two steps, wherein if x
matches with more than one of said vertices in the second
set, vertex y being selected at random: e-1)(23.9) adding new matching (x,y) if y is not part
of any previous matching; and e-2)(23.11) replacing a matching involving y by a
matching (x,y) if y is already part of a matching (z,y),
wherein z is a vertex in said first set; and f)(23.5, 23.10) repeating step (e) for each
unmatched vertex in said first set.
Claim 2
Dependent Claim
313 words
A computer-implemented weighted queuing
method for a system with M groups of N input queues each
of said N input queues requesting a unique one of N services,
wherein M and N are natural numbers, characterized by the
steps of: a)(24.1) representing each of said M groups as
a node in a first set of vertices of a bipartite graph; b)(24.2) representing each of said N services
as a node in a second set of vertices of said bipartite
graph; c)(24.3) representing each non-empty queue as
an edge between a vertex in said first set corresponding
to one of said M groups to which said each non-empty queue
belongs to and a vertex in said second set corresponding
to a service requested by said each non-empty queue; d)(24.4) performing an initial matching by
finding a subset of edges such that no vertex is incident
to more than one edge in such subset, wherein if a vertex
can be matched using more than one edges, one edge is
selected from said more than one edges with a probability
relative to the size of queues associated with each of said
one or more edges; e)(24.6-24.11) performing a weighted shakeup
matching by performing an appropriate one of following two
steps for a hitherto unmatched vertex x in said first set
to a vertex y in the second set: e-1)(24.7) if y is not part of any previous matching,
said vertex y being selected with a probability: wherein q xy is a length of a queue between vertices x and
Y; e-2)(24.11) replacing a matching involving y by a
matching (x,y) if y is already part of a matching (z,y),
said replacement being done with a probability: q xy q xy + q zy wherein z is a vertex in said first set; and f)(24.5, 24.10) repeating step (e) for each
unmatched vertex in said first set.
Claim 3
Independent Claim
287 words
A method of unweighted routing in a switch
comprising input ports and output ports, having cells to
route between said input ports and said output ports, each
input port having one queue each for each said output port,
thereby each input port having as many queues as a number
of said output ports, characterized by the steps of: a) representing each said input pods as a node
in a first set of vertices of a bipartite graph; b) representing each said output ports as a node
in a second set of vertices of said bipartite graph; c) representing each non-empty queue between
any of said input ports and any of said output ports as
an edge between a vertex in said first set corresponding
to said any of said input ports and a vertex in said second
set corresponding to said any of said output ports, thereby
creating a set of edges; d) performing an initial matching by finding
a subset of edges such that no vertex is incident to more
than one edge in said subset; e) performing an unweighted shakeup matching
for a hitherto unmatched vertex x in said first set to a
vertex y in the second set by performing an appropriate
one of the following two steps, wherein if x matches with
more than one of said vertices in the second set, vertex
y being selected at random: e-1) adding new matching (x,y) if y is not part of
any previous matching; e-2) replacing a matching involving y by a matching
(x,y) if y is already part of a matching (z,y) wherein z
is a vertex in said first set; and f) repeating step (e) for each unmatched vertex
in said first set.
Claim 4
Independent Claim
340 words
A method of weighted routing in a switch
comprising input ports and output ports, having cells to
route between said input ports and said output ports, each
input port having one queue each for each said output port,
thereby each input port having as many queues as a number
of said output ports, characterized by the steps of: a) representing each said input ports as a node
in a first set of vertices of a bipartite graph; b ) representing each said output ports as a node
in a second set of vertices of said bipartite graph; c) representing each non-empty queue between
any of said input ports and any of said output ports as
an edge between a vertex in said first set corresponding
to said any of said input ports and a vertex in said second
set corresponding to said any of said output ports, thereby
creating a set of edges; d) performing an initial matching by finding
a subset of edges such that no vertex is incident to more
than one edge in such subset, wherein if a vertex can be
matched using more than one edges, one edge is selected
from said more than one edges with a probability relative
to a size of a queue associated with each of said one or
more edges; e) performing a weighted shakeup matching by
performing an appropriate one of following two steps for
a hitherto unmatched vertex x in said first set to a vertex
y in the second set: e-1) if y is not part of any previous matching, said
vertex y being selected with a probability: wherein q xy is a length of a queue between vertices x and
Y; e-2) replacing a matching involving y by a matching
(x,y) if y is already part of a matching (z,y), said
replacement being done with a probability: q xy q xy + q zy wherein z is a vertex in said first set; and f ) repeating step (e) for each unmatched vertex
in said first set.
Claim 5
Dependent Claim
15 words
The method of claim 3 wherein said unweighted
shakeup is performed for every alternate matching.
Claim 6
Dependent Claim
15 words
The method of claim 4 wherein said weighted
shakeup is performed for every alternate matching.
Claim 7
Dependent Claim
24 words
The method of claim 3 wherein said unweighted
shakeup is performed only if no increase in the size of
matching is possible without shakeup.
Claim 8
Dependent Claim
24 words
The method of claim 4 wherein said weighted
shakeup is performed only if no increase in the size of
matching is possible without shakeup.
Claim 9
Dependent Claim
205 words
An unweighted shakeup switch for use in a
network, said switch comprising: input ports (25.11-25.14); output ports(25.51-25.54), wherein cells are
routed between said input ports and said output ports; and an unweighted scheduler, wherein said unweighted scheduler further
comprises: a graph generator (25.2) that generates a bipartite
graph with each said input ports as a node in a first set
of vertices of the bipartite graph and each said output
ports is a node in a second set of vertices of said bipartite
graph and a cell to be routed between an input port and
an output port is an edge between a vertex in said first
set said second set; a matcher (25.3) for performing an initial matching
by finding a subset of edges such that no vertex is incident
to more than one edge in such subset; an unweighted shakeup matcher (25.4) for performing
an unweighted shakeup matching for a hitherto unmatched
vertex x in said first set to a vertex y in the second set,
wherein said unweighted shakeup matcher adds new matching
(x,y) if y is not part of any previous matching and replaces
a matching involving y by a matching (x,y) if y is already
part of a matching (z,y).
Claim 10
Dependent Claim
240 words
A weighted shakeup switch for use in a network,
said switch comprising: input ports (26.11-26.14); output ports (26.51-26.54), wherein cells are
routed between said input ports and said output ports; and a weighted scheduler, wherein said weighted scheduler further
comprises: a graph generator (26.2) that generates a bipartite
graph with each said input ports as a node in a first set
of vertices of the bipartite graph and each said output
ports is a node in a second set of vertices of said bipartite
graph and a cell to be routed between an input port and
an output port is an edge between a vertex in said first
set said second set; a matcher (26.3) for performing an initial matching
by finding a subset of edges such that no vertex is incident
to more than one edge in such subset; a weighted shakeup matcher (26.4) for performing a
weighted shakeup matching for a hitherto unmatched vertex
x in said first set to a vertex y in the second set, wherein
said weighted shakeup matcher adds (x,y) if y is not part
of any previous matching, said vertex y being selected with
a probability: wherein q xy is a length of a queue between vertices x and
y, and replaces a matching involving y by a matching (x,y)
if y is already part of a matching (z,y), said replacement
being done with a probability: q xy q xy + q zy
Claim 11
Dependent Claim
15 words
The switch of claim 9 wherein said unweighted
shakeup is performed for every alternate matching.
Claim 12
Dependent Claim
15 words
The switch of claim 10 wherein said weighted
shakeup is performed for every alternate matching.
Claim 13
Dependent Claim
24 words
The switch of claim 9 wherein said unweighted
shakeup is performed only if no increase in the size of
matching is possible without shakeup.
Claim 14
Dependent Claim
24 words
The switch of claim 10 wherein said weighted
shakeup is performed only if no increase in the size of
matching is possible without shakeup.
Claim 15
Dependent Claim
475 words
A network system comprising a plurality of
switches for routing messages, a first subset of the
plurality of said switches being unweighted shakeup
switches, a second subset of the plurality of said switches
being weighted shakeup switches, each of the unweighted shakeup switches
comprising: input ports (25.11-25.14); output
ports(25.51-25.54), wherein cells are routed between said
input ports and said output ports; and an unweighted
scheduler, wherein said unweighted scheduler further
comprises: a graph generator (25.2) that generates a bipartite
graph with each said input ports as a node in a first set
of vertices of the bipartite graph and each said output
ports is a node in a second set of vertices of said bipartite
graph and a cell to be routed between an input port and
an output port is an edge between a vertex in said first
set said second set; a matcher (25.3) for performing an initial matching
by finding a subset of edges such that no vertex is incident
to more than one edge in such subset; and an unweighted shakeup matcher (25.4) for performing
an unweighted shakeup matching for a hitherto unmatched
vertex x in said first set to a vertex y in the second set,
wherein said unweighted shakeup matcher adds new matching
(x,y) if y is not part of any previous matching and replaces
a matching involving y by a matching (x,y) if y is already
part of a matching (z,y), and each of the weighted shakeup switches
comprising: input ports (26.11-26.14); output ports
(26.51-26.54), wherein cells are routed between said input
ports and said output ports; and a weighted scheduler,
wherein said weighted scheduler further comprises: a graph generator (26.2) that generates a bipartite
graph with each said input ports as a node in a first set
of vertices of the bipartite graph and each said output
ports is a node in a second set of vertices of said bipartite
graph and a cell to be routed between an input port and
an output port is an edge between a vertex in said first
set said second set; a matcher (26.3) for performing an initial matching
by finding a subset of edges such that no vertex is incident
to more than one edge in such subset; and a weighted shakeup matcher (26.4) for performing a
weighted shakeup matching for a hitherto unmatched vertex
x in said first set to a vertex y in the second set, wherein
said weighted shakeup matcher adds (x,y) if y is not part
of any previous matching, said vertex y being selected with
a probability: wherein q xy is a length of a queue between vertices x and
y, and replaces a matching involving y by a matching (x,y)
if y is already part of a matching (z,y), said replacement
being done with a probability: q xy q xy + q zy
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.