Two-component bandwidth scheduler having application in multi-class digital communications systems

Number of patents in Portfolio can not be more than 2000

United States of America Patent

PATENT NO 6438134
SERIAL NO

09140059

Stats

ATTORNEY / AGENT: (SPONSORED)

Importance

Loading Importance Indicators... loading....

Abstract

See full text

The method for servicing queues holding messages, such as ATM data packets, for subsequent processing or transmission to a resource such as a communications link having a finite processing capability comprises the steps of servicing each queue by forwarding the messages thereof to the resource at time intervals corresponding to a guaranteed service rate of the queue, provided the queue is non-empty; and, during time intervals when none of the queues have messages being forwarded to the resource in conformance with the above step, servicing the queues in accordance with a proportion of a remaining or idle resource bandwidth allocated to each queue. The method is preferably carried out by a hierarchical scheduler comprising an exhaustive sub-scheduler servicing a plurality of lower level sub-schedulers in accordance with non-equal priority levels assigned thereto; M non-work conserving shaper sub-schedulers feeding the exhaustive sub-scheduler; and N work conserving idle bandwidth sub-schedulers feeding the exhaustive sub-scheduler. In such a scheduler, a queue concurrently contends for service by one of the shaper sub-schedulers and one of the idle bandwidth sub-schedulers, wherein the shaper sub-scheduler servicing the queue has a higher priority level with respect to the exhaustive sub-scheduler than the idle bandwidth sub-scheduler servicing the same queue. The technique distributes the idle bandwidth of the resource in a way which is de-coupled from the guaranteed service rates of the queues, thereby providing a more efficient bandwidth distribution.

Loading the Abstract Image... loading....

First Claim

See full text

Family

Loading Family data... loading....

Patent Owner(s)

Patent OwnerAddressTotal Patents
ALCATEL-LUCENT CANADA INC.KANATA ONTARIO71

International Classification(s)

  • [Classification Symbol]
  • [Patents Count]

Inventor(s)

Inventor Name Address # of filed Patents Total Citations
Chow, Henry Kanata, CA 11 423
Hung, Anthony Ottawa, CA 9 242
Janoska, Mark Carleton Place, CA 1 147
Ramaswamy, Srinivasan Ottawa, CA 21 453

Cited Art Landscape

Patent Info (Count) # Cites Year
 
RPX CLEARINGHOUSE LLC (1)
* 6018527 Queue service interval based cell scheduler with hierarchical queuing configurations 72 1996
 
THE REGENTS OF THE UNIVERSITY OF CALIFORNIA (1)
* 6134217 Traffic scheduling system and method for packet-switched networks with fairness and low latency 126 1996
 
EXTREME NETWORKS, INC. (1)
* 6272109 Hierarchical schedules for different ATM traffic 91 1997
 
INTEL CORPORATION (1)
* 5959993 Scheduler design for ATM switches, and its implementation in a distributed shared memory architecture 37 1996
 
THE HONG KONG UNIVERSITY OF SCIENCE AND TECHNOLOGY (1)
* 6047000 Packet scheduling system 41 1997
 
PROVENANCE ASSET GROUP LLC (2)
* 5850399 Hierarchical packet scheduling method and apparatus 202 1998
* 5905730 High speed packet scheduling method and apparatus 100 1998
* Cited By Examiner

Patent Citation Ranking

Forward Cite Landscape

Patent Info (Count) # Cites Year
 
Other [Check patent profile for assignment information] (1)
* 2002/0080,796 Packet switch 3 2001
 
PASSAVE LTD. (1)
* 2008/0181,248 METHODS FOR DYNAMIC BANDWIDTH ALLOCATION AND QUEUE MANAGEMENT IN ETHERNET PASSIVE OPTICAL NETWORKS 8 2008
 
SONY CORPORATION OF AMERICA (1)
RE41849 Parallel multi-threaded processing 0 2005
 
TAIWAN SEMICONDUCTOR MANUFACTURING COMPANY, LTD. (4)
* 9065779 Systems and methods for prioritizing and scheduling packets in a communication network 3 2011
* 2012/0008,499 SYSTEMS AND METHODS FOR PRIORITIZING AND SCHEDULING PACKETS IN A COMMUNICATION NETWORK 5 2011
9065777 Systems and methods for prioritizing and scheduling packets in a communication network 1 2014
9237112 Systems and methods for prioritizing and scheduling packets in a communication network 0 2015
 
CALIX, INC. (2)
* 9185042 System and method for automated quality of service configuration through the access network 0 2013
* 2015/0063,107 SYSTEM AND METHOD FOR AUTOMATED QUALITY OF SERVICE CONFIGURATION THROUGH THE ACCESS NETWORK 1 2013
 
BARRACUDA NETWORKS, INC. (1)
* 2007/0242,675 Dual scheduling for efficient network traffic management 4 2006
 
PALMSOURCE, INC. (1)
* 7570942 Transactional message-queue communication for wirelessly networked devices system and method 0 2005
 
MELLANOX TECHNOLOGIES LTD. (2)
* 8194690 Packet processing in a parallel processing environment 17 2007
9787612 Packet processing in a parallel processing environment 0 2012
 
ORACLE AMERICA, INC. (1)
* 6721789 Scheduling storage accesses for rate-guaranteed and non-rate-guaranteed requests 47 1999
 
FORE SYSTEMS, INC. (1)
* 7304945 Method and apparatus for dynamic bitmap generator scheduler 3 2000
 
AVAYA INC. (1)
* 7397762 System, device and method for scheduling information processing with load-balancing 7 2002
 
LOCKHEED MARTIN CORPORATION (2)
7889743 Information dissemination method and system having minimal network bandwidth utilization 5 2007
* 2008/0259,927 Information dissemination method and system having minimal network bandwidth utilization 8 2007
 
MINERAL LASSEN LLC (5)
* 7856011 Reordering packets 3 2005
* 2006/0072,578 Reordering packets 18 2005
8107377 Reordering packets 1 2010
* 2010/0189,123 Reordering Packets 2 2010
8913618 Reordering packets 0 2011
 
INTERNATIONAL BUSINESS MACHINES CORPORATION (9)
* 6952424 Method and system for network processor scheduling outputs using queueing 20 2000
* 6862292 Method and system for network processor scheduling outputs based on multiple calendars 6 2000
* 7123622 Method and system for network processor scheduling based on service levels 6 2001
* 2002/0023,168 Method and system for network processor scheduling based on service levels 5 2001
* 7382792 Queue scheduling mechanism in a data packet transmission system 0 2002
* 2003/0099,250 Queue scheduling mechanism in a data packet transmission system 1 2002
8218551 Hierarchical scheduling 0 2003
* 2005/0071,504 Hierarchical scheduling 5 2003
* 2005/0071,503 Hierarchical scheduling 0 2003
 
EXTREME NETWORKS, INC. (1)
* 7936770 Method and apparatus of virtual class of service and logical queue representation through network traffic distribution over multiple port interfaces 132 2006
 
LUCENT TECHNOLOGIES INC. (3)
* 7408946 Systems and methods for smooth and efficient round-robin scheduling 1 2004
* 2005/0243,847 Systems and methods for smooth and efficient round-robin scheduling 2 2004
* 2008/0002,577 Efficient allocation of shapers 1 2006
 
SIEMENS AKTIENGESELLSCHAFT (1)
* 2002/0083,207 Method and system for accessing an IP network and for working in it 2 2001
 
KONSULTOINTI MARTIKAINEN OY (2)
* 8316372 Method for multiclass task allocation 0 2009
* 2011/0093,860 METHOD FOR MULTICLASS TASK ALLOCATION 2 2009
 
CISCO TECHNOLOGY, INC. (22)
* 7065762 Method, apparatus and computer program product for borrowed-virtual-time scheduling 8 1999
* 7392279 Network traffic shaping using time-based queues 24 1999
6775232 Method for scheduling data for communication on a digital subscriber line 22 2000
* 7212494 In-band must-serve indication from scheduler to switch fabric 3 2001
* 7385987 Scheduling system and method for multi-level class hierarchy 7 2003
* 7277448 Hierarchical scheduler inter-layer eligibility deferral 11 2003
* 7876763 Pipeline scheduler including a hierarchy of schedulers and multiple scheduling lanes 7 2004
* 2006/0029,079 Pipeline scheduler including a hierarchy of schedulers and multiple scheduling lanes 34 2004
7599381 Scheduling eligible entries using an approximated finish delay identified for an entry based on an associated speed group 1 2004
7522609 Propagation of minimum guaranteed scheduling rates among scheduling layers in a hierarchical schedule 8 2004
* 2006/0153,243 Scheduling eligible entries using an approximated finish delay identified for an entry based on an associated speed group 3 2004
* 2005/0152,374 Propagation of minimum guaranteed scheduling rates among scheduling layers in a hierarchical schedule 14 2004
8077618 Using burst tolerance values in time-based schedules 1 2005
* 2006/0029,080 Using burst tolerance values in time-based schedules 12 2005
8018845 Sampling rate-limited traffic 8 2006
* 2007/0171,824 Sampling rate-limited traffic 92 2006
* 7921422 Method, apparatus and computer program product for borrowed-virtual-time scheduling 0 2006
* 2007/0150,898 Method, apparatus & computer program product for borrowed-virtual-time scheduling 13 2006
8077611 Multilevel coupled policer 1 2006
* 2008/0025,214 Multilevel coupled policer 19 2006
8325736 Propagation of minimum guaranteed scheduling rates among scheduling layers in a hierarchical schedule 1 2009
* 2009/0207,846 PROPAGATION OF MINIMUM GUARANTEED SCHEDULING RATES AMONG SCHEDULING LAYERS IN A HIERARCHICAL SCHEDULE 3 2009
 
KONINKLIJKE KPN N.V. (1)
* 6850881 ATM connection admission control device for DBR connections 0 2001
 
FUJITSU LIMITED (4)
* 7023865 Packet switch 3 2001
* 2003/0147,398 Packet switch 0 2001
* 7752310 Computer program, method, and apparatus for managing reservation of it resources 17 2006
* 2007/0165,525 Computer program, method, and apparatus for managing reservation of it resources 20 2006
 
MOTOROLA, INC. (1)
* 2005/0047,415 Data traffic manager and method therefor 10 2003
 
WORLD WIDE PACKETS, INC. (6)
7272149 Bandwidth allocation systems and methods 20 2002
7272150 System and method for shaping traffic from a plurality of data streams using hierarchical queuing 5 2002
* 2004/0032,830 System and method for shaping traffic from a plurality of data streams using hierarchical queuing 6 2002
* 7277389 Systems and methods for grouping of bandwidth allocations 1 2002
* 2004/0042,399 Systems and methods for grouping of bandwidth allocations 0 2002
7269180 System and method for prioritizing and queuing traffic 5 2002
 
ORANGE (1)
* 7933204 Method for organizing packets belonging to streams, and associated equipment 0 2006
 
CUFER ASSET LTD. L.L.C. (14)
6976258 Providing quality of service guarantees to virtual hosts 62 1999
6754716 Restricting communication between network devices on a common network 72 2000
6948003 Enabling a service provider to provide intranet services 56 2000
6985937 Dynamically modifying the resources of a virtual server 161 2000
6907421 Regulating file access rates according to file type 15 2000
7143024 Associating identifiers with virtual processes 14 2000
* 6909691 Fairly partitioning resources while limiting the maximum fair share 38 2000
7219354 Virtualizing super-user privileges for multiple virtual processes 29 2000
RE44723 Regulating file access rates according to file type 0 2007
RE43051 Enabling a service provider to provide intranet services 6 2007
RE42214 Providing quality of service guarantees to virtual hosts 1 2007
RE42726 Dynamically modifying the resources of a virtual server 11 2008
RE44210 Virtualizing super-user privileges for multiple virtual processes 0 2009
RE44686 Dynamically modifying the resources of a virtual server 4 2011
 
AT&T INTELLECTUAL PROPERTY II, L.P. (1)
* 7545815 Queueing technique for multiple sources and multiple priorities 0 2004
 
PROVENANCE ASSET GROUP LLC (2)
* 7075934 Method and apparatus for hierarchical bandwidth distribution in a packet network 39 2001
* 2003/0169,743 Method and apparatus for hierarchical bandwidth distribution in a packet network 0 2001
 
INTEL CORPORATION (20)
7620702 Providing real-time control data for a network processor 2 1999
7480706 Multi-threaded round-robin receive for fast network port 8 2000
* 7471688 Scheduling system for transmission of cells to ATM virtual circuits and DSL ports 3 2002
7352769 Multiple calendar schedule reservation structure and method 14 2002
7433307 Flow control in a network environment 18 2002
7443836 Processing a data packet 17 2003
7751402 Method and apparatus for gigabit packet assignment for multithreaded packet processing 7 2003
* 7031255 Method and apparatus for guaranteeing data transfer rates and delays in data packet networks using generalized discrete data transfer rate approach 1 2003
* 2004/0151,167 Method and apparatus for guaranteeing data transfer rates and delays in data packet networks using generalized discrete data transfer rate approach 0 2003
8738886 Memory mapping in a processor having multiple programmable units 0 2004
7328289 Communication between processors 12 2004
* 7646779 Hierarchical packet scheduler using hole-filling and multiple packet buffering 7 2004
* 7525962 Reducing memory access bandwidth consumption in a hierarchical packet scheduler 5 2004
* 2006/0153,184 Reducing memory access bandwidth consumption in a hierarchical packet scheduler 6 2004
7424579 Memory controller for processor having multiple multithreaded programmable units 18 2005
7434221 Multi-threaded sequenced receive for fast network port stream of packets 21 2005
* 7801164 Two dimensional timeout table mechanism with optimized delay characteristics 0 2006
* 2007/0253,451 Two dimensional timeout table mechanism with optimized delay characteristics 1 2006
8316191 Memory controllers for processor having multiple programmable units 4 2008
9128818 Memory mapping in a processor having multiple programmable units 0 2014
 
MITSUBISHI DENKI KABUSHIKI KAISHA (1)
* 2004/0174,881 Packet scheduling system and a packet scheduling method 2 2004
 
SYMANTEC CORPORATION (2)
* 7551623 Modulation of partition parameters achieving delay-based QoS mechanism 25 2005
* 9755984 Aggregate network resource utilization control scheme 0 2008
 
NVIDIA CORPORATION (2)
* 7729307 Scheduling data across a shared communication link in a cellular communication system 4 2004
* 2006/0056,373 Scheduling data across a shared communication link in a cellular communication system 13 2004
 
CHANYU HOLDINGS, LLC (2)
* 8018925 System and method for multi-services packet network traffic engineering 9 2010
* 2010/0296,474 System And Method For Multi-Services Packet Network Traffic Engineering 32 2010
 
SONY COMPUTER ENTERTAINMENT INC. (1)
* 7099975 Method of resource arbitration 2 2003
 
SERIQA NETWORKS (1)
* 2004/0042,398 Method and apparatus for reducing traffic congestion by preventing allocation of the occupied portion of the link capacity and for protecting a switch from congestion by preventing allocation on some of its links 32 2003
 
III HOLDINGS 12, LLC (3)
* 8930536 Virtual private cluster 0 2006
* 2006/0212,740 Virtual Private Cluster 19 2006
9225663 System and method providing a virtual private cluster 0 2015
 
JUNIPER NETWORKS, INC. (18)
* 7120114 Call admission control method and system 8 2000
* 8078763 Dequeuing and congestion control systems and methods for single stream multicast 8 2002
* 7382793 Systems and methods for determining the bandwidth used by a queue 12 2002
* 9031079 Hierarchical shaping of network traffic 1 2004
7616564 Call admission control method and system 2 2006
* 8295172 Network device traffic class mapping function 1 2007
7711005 Systems and methods for determining the bandwidth used by a queue 6 2008
7920471 Call admission control method and system 1 2009
* 2010/0020,805 CALL ADMISSION CONTROL METHOD AND SYSTEM 1 2009
7885281 Systems and methods for determining the bandwidth used by a queue 6 2010
8599868 Systems and methods for determining the bandwidth used by a queue 0 2010
* 2011/0096,689 SYSTEMS AND METHODS FOR DETERMINING THE BANDWIDTH USED BY A QUEUE 6 2010
8369215 Call admission control method and system 1 2011
8681681 Dequeuing and congestion control systems and methods for single stream multicast 1 2011
8711694 Call admission control method and system 0 2013
8913541 Dequeuing and congestion control systems and methods for single stream multicast 0 2014
9100314 Dequeuing and congestion control systems and methods for single stream multicast 0 2014
9363186 Hierarchical shaping of network traffic 0 2015
 
POINT REYES NETWORKS, INC. (1)
* 6570883 Packet scheduling using dual weight single priority queue 70 1999
 
NOKIA TECHNOLOGIES OY (2)
* 7626989 Capacity allocation for packet data bearers 7 2001
* 2005/0276,256 Capacity allocation for packet data bearers 11 2003
 
RIVERSTONE NETWORKS, INC. (1)
* 6636480 Method and system for controlling data flow through a multiport switch 15 1999
 
Radioscape Limited (1)
* 2005/0246,712 Method of designing a system for real time digital signal processing, in which the system uses a virtual machine layer 10 2005
 
DRAGONWAVE INC. (1)
7957291 Apparatus and methods for controlling effective communication traffic rates 3 2007
 
MICROSEMI STORAGE SOLUTIONS, INC. (2)
* 7486686 Method and apparatus for scheduling data on a medium 1 2002
* 2002/0167,957 Method and apparatus for scheduling data on a medium 8 2002
 
FUJITSU NETWORK COMMUNICATIONS, INC. (1)
* 6628668 Crosspoint switch bandwidth allocation management 58 1999
 
A10 NETWORKS, INC. (5)
* 7236491 Method and apparatus for scheduling for packet-switched networks 54 2001
* 2002/0131,413 Method and apparatus for scheduling for packet-switched networks 27 2001
9154577 Sychronization of configuration file of virtual application distribution chassis 5 2011
9477563 Virtual application delivery chassis system 1 2014
9596134 Synchronization of configuration file of virtual application distribution chassis 0 2015
 
ALCATEL CANADA INC. (2)
7061918 Fair share scheduling of multiple service classes with prioritized shaping 5 2004
* 2004/0160,961 Fair share scheduling of multiple service classes with prioritized shaping 6 2004
 
WSOU INVESTMENTS, LLC (1)
* 6529474 Shaping algorithm 6 1999
 
NEC CORPORATION (1)
* 6697863 Method and packet-processing device for use in an active node included in an active network to allocate a sequence of packets received by the active node 13 1999
 
FUTUREWEI TECHNOLOGIES, INC. (3)
* 6891834 Apparatus and method for packet scheduling 37 2000
* 7760747 Apparatus and method for packet scheduling 6 2005
* 2005/0163,140 Apparatus and method for packet scheduling 6 2005
 
INTELLECTUAL VENTURES I LLC (3)
7343421 Restricting communication of selected processes to a set of specific network addresses 16 2000
7739401 Restricting communication of selected processes to a set of specific network addresses 11 2008
8489764 Restricting communication of selected processes to a set of specific network addresses 0 2010
 
MICROSOFT TECHNOLOGY LICENSING, LLC (1)
* 2005/0030,896 Adaptively changing weights for fair scheduling in broadcast environments 4 2004
 
GOOGLE TECHNOLOGY HOLDINGS LLC (2)
* 7385993 Queue scheduling mechanism in a data packet transmission system 5 2002
* 2003/0118,044 Queue scheduling mechanism in a data packet transmission system 4 2002
 
ELECTRONICS AND TELECOMMUNICATIONS RESEARCH INSTITUTE (5)
* 7233893 Method and apparatus for transmitting wideband speech signals 10 2002
7467082 Method and apparatus for transmitting wideband speech signals 8 2007
* 2007/0213,976 METHOD AND APPARATUS FOR TRANSMITTING WIDEBAND SPEECH SIGNALS 0 2007
8010346 Method and apparatus for transmitting wideband speech signals 0 2008
8340959 Method and apparatus for transmitting wideband speech signals 0 2011
 
MICROSEMI ISRAEL STORAGE SOLUTIONS LTD. (3)
* 7920593 Methods for dynamic bandwidth allocation and queue management in Ethernet passive optical networks 2 2008
8644143 Methods for dynamic bandwidth allocation and queue management in ethernet passive optical networks 1 2011
* 2011/0182,579 METHODS FOR DYNAMIC BANDWIDTH ALLOCATION AND QUEUE MANAGEMENT IN ETHERNET PASSIVE OPTICAL NETWORKS 1 2011
 
AVAGO TECHNOLOGIES GENERAL IP (SINGAPORE) PTE. LTD. (7)
7161906 Three-stage switch fabric with input device features 32 2001
* 7158528 Scheduler for a packet routing and switching system 23 2001
7023841 Three-stage switch fabric with buffered crossbar devices 27 2001
* 2002/0136,230 Scheduler for a packet routing and switching system 63 2001
* 2002/0085,578 Three-stage switch fabric with buffered crossbar devices 42 2001
* 2002/0075,883 Three-stage switch fabric with input device features 44 2001
* 2003/0147,349 Communications systems and methods utilizing a device that performs per-service queuing 7 2002
 
QUALCOMM INCORPORATED (1)
* 2004/0233,939 Method and apparatus for proportionately multiplexing data streams onto one data stream 2 2004
 
SHARP KABUSHIKI KAISHA (6)
* 7024482 Pseudo-random dynamic scheduler for scheduling communication periods between electronic devices 7 2001
* 2002/0147,816 Pseudo-random dynamic scheduler for scheduling communication periods between electronic devices 3 2001
8069254 Communication period management in a communication system 1 2002
* 2003/0088,682 Communication period management in a communication system 6 2002
* 2006/0129,679 Pseudo-random dynamic scheduler for scheduling communication periods between electronic devices 6 2006
8583805 Communication period management in a communication system 0 2011
 
AMPLIFY.NET, INC. (1)
* 2003/0099,199 Bandwidth allocation credit updating on a variable time basis 11 2001
 
PIONEER CORPORATION (1)
* 2005/0151,756 Information delivery display system and information delivery display method 8 2005
 
TELEFONAKTIEBOLAGET L M ERICSSON (PUBL) (5)
* 6850540 Packet scheduling in a communications system 74 2000
* 6917591 Methods, systems and computer program products for bandwidth allocation in a multiple access system 20 2001
* 2002/0136,200 Methods, systems and computer program products for bandwidth allocation in a multiple access system 4 2001
* 8270298 Method and arrangement for flow control in UMTS using information in UBS field 1 2005
* 2009/0221,292 METHOD AND ARRANGEMENT FOR FLOW CONTROL IN UMTS USING INFORMATION IN UBS FIELD 5 2005
 
PALM, INC. (1)
* 2006/0135,130 Transactional message-queue communication for wirelessly networked devices system and method 0 2005
 
PARITY NETWORKS LLC (1)
* 7016302 Apparatus and method for controlling queuing of data at a node on a network 8 2000
 
RPX CLEARINGHOUSE LLC (3)
* 6501762 Scheduler implementing weighted fair queuing by a weight limited first in-first out methodology 15 1999
* 7995597 Method and system for weighted fair queuing 2 2008
* 2010/0091,783 METHOD AND SYSTEM FOR WEIGHTED FAIR QUEUING 2 2008
 
WI-LAN LABS, INC. (1)
8995273 Systems and methods for prioritizing and scheduling packets in a communication network 0 2014
 
RPX CORPORATION (1)
* 6625122 Selection of data for network transmission 7 1999
 
SYNAPTICS INCORPORATED (2)
* 7142514 Bandwidth sharing using emulated weighted fair queuing 6 2001
* 2002/0039,351 Bandwidth sharing using emulated weighted fair queuing 2 2001
 
Koninklijke KPN N.V. (2)
6907467 ATM connection admission control device for DBR connections 1 2004
* 2005/0038,903 ATM connection admission control device for DBR connections 1 2004
 
TROPIC NETWORKS INC. (2)
* 7266606 Cascaded policing systems and methods 3 2001
* 2003/0018,801 Cascaded policing systems and methods 1 2001
 
ALCATEL (2)
* 6680907 Shaping method, a shaper realizing such a shaping method and communication network including such a shaper 14 1999
6868063 Shaping method and related shaper 6 2000
 
F. POSZAT HU, L.L.C. (2)
* 6765867 Method and apparatus for avoiding head of line blocking in an ATM (asynchronous transfer mode) device 13 2002
* 2003/0202,516 Method and apparatus for avoiding head of line blocking in an ATM (asynchronous transfer mode) device 1 2002
 
POWER IP, LLC (2)
* 6938093 Bandwidth allocation for a data path 1 2002
* 2003/0037,205 Bandwidth allocation for a data path 0 2002
 
AT&T CORP. (1)
* 2006/0083,226 Queueing technique for multiple sources and multiple priorities 3 2004
* Cited By Examiner