Rate shaping in per-flow queued routing mechanisms for available bit rate service

Number of patents in Portfolio can not be more than 2000

United States of America Patent

PATENT NO 5926459
SERIAL NO

08872753

Stats

ATTORNEY / AGENT: (SPONSORED)

Importance

Loading Importance Indicators... loading....

Abstract

See full text

Rate shaping is provided in per-flow queued routing mechanisms for available bit rate service. A traffic shaper in a packet switched communications system serially emits packets of time multiplexed flows in substantial compliance with individual network traffic contracts for the respective flows. The individual network traffic contracts include contracts which specify respective peak packet emission rates and associated peak rate tolerances for certain of the flows and which cause each of the flows to fall into mutually exclusive categories. The traffic shaper includes a queuing mechanism and a scheduling mechanism. The queuing mechanism organizes pending packets of active flows, including the certain flows, in respective queues in accordance with an oldest pending packet at head of queue order. The scheduling mechanism is coupled to the queuing mechanism for scheduling the packets of the active flows for emission. The scheduling mechanism includes a relatively high priority non-work conserving calendar queue, at least one relatively low priority work conserving queue, and another non-working conserving calendar queue of indeterministic priority relative to the high and low priority queues. The scheduling mechanism can also include a control mechanism for monitoring emissions from the high and low priority queues and for selectively descheduling packets scheduled on the high and low priority queues.

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

First Claim

See full text

Family

Loading Family data... loading....

Patent Owner(s)

Patent OwnerAddressTotal Patents
XEROX CORPORATIONSTAMFORD, CT13750

International Classification(s)

  • [Classification Symbol]
  • [Patents Count]

Inventor(s)

Inventor Name Address # of filed Patents Total Citations
Kappler, Christopher J Charlestown, MA 19 514
Lyles, J Bryan Mountain View, CA 6 391
Rogers, Landis C Kingston, NH 5 281

Cited Art Landscape

Patent Info (Count) # Cites Year
 
AVAYA HOLDINGS LIMITED (1)
* 5497371 Digital telecommunication link for efficiently transporting mixed classes of packets 126 1995
 
AT&T IPM CORP. (1)
* 5463620 Bandwidth allocation, transmission scheduling, and congestion avoidance in broadband asynchronous transfer mode networks 305 1994
 
FRANCE TELECOM (1)
* 5400336 Method for controlling the delivery from cells 20 1992
 
MOTOROLA, INC. (2)
* 5231633 Method for prioritizing, selectively discarding, and multiplexing differing traffic type fast packets 354 1990
* 5793747 Event-driven cell scheduler and method for supporting multiple service categories in a communication network 190 1996
* Cited By Examiner

Patent Citation Ranking

Forward Cite Landscape

Patent Info (Count) # Cites Year
 
Other [Check patent profile for assignment information] (2)
* 2007/0081,456 PRIORITY BASED BANDWIDTH ALLOCATION WITHIN REAL-TIME AND NON-REAL TIME TRAFFIC STREAMS 4 2006
* 2008/0107,118 WEIGHTED FAIR QUEUE SERVING PLURAL OUTPUT PORTS 2 2008
 
ENPLUG, INC. (1)
* 7277931 Representing, configuring, administering, monitoring, and/or modeling connections using catalogs and matrixes 22 1999
 
MICROSEMI STORAGE SOLUTIONS LTD. (1)
6996107 Packet shaping on a fixed segment scheduler 12 2001
 
EMC IP HOLDING COMPANY LLC (2)
7546367 Methods and systems for managing network traffic by multiple constraints 5 2004
* 2005/0169,173 Methods and systems for managing network traffic by multiple constraints 12 2004
 
JUNIPER NETWORKS, INC. (7)
* 8271672 Guaranteed bandwidth memory apparatus and method 2 2001
7698454 Interfacing with streams of differing speeds 3 2001
* 7457247 Collision compensation in a scheduling system 4 2004
8107372 Collision compensation in a scheduling system 0 2008
8131854 Interfacing with streams of differing speeds 0 2010
* 2010/0138,554 INTERFACING WITH STREAMS OF DIFFERING SPEEDS 0 2010
8706896 Guaranteed bandwidth memory apparatus and method 0 2012
 
XEROX CORPORATION (1)
* 6377583 Rate shaping in per-flow output queued routing mechanisms for unspecified bit rate service 88 1997
 
VULCAN VENTURES, INC. (2)
7036138 Method and apparatus for scheduling broadcast information 31 2000
6732325 Error-correction with limited working storage 99 2000
 
SEABRIDGE LTD. (2)
* 6947996 Method and system for traffic control 23 2001
* 2002/0147,829 Method and system for traffic control 2 2001
 
IKANOS COMMUNICATIONS, INC. (1)
* 2002/0150,047 System and method for scheduling transmission of asynchronous transfer mode cells 27 2002
 
MELLANOX TECHNOLOGIES LTD. (1)
7149227 Round-robin arbiter with low jitter 51 2002
 
FUJITSU NETWORK COMMUNICATIONS, INC. (1)
* 6195333 Unframed isochronous shaping method to reduce delay and delay variation in a CBR transmission system 15 1997
 
ZARBAÑA DIGITAL FUND LLC (4)
* 7194741 Weighted fair queuing scheduler 8 2002
* 2003/0050,954 Weighted fair queuing scheduler 21 2002
* 7461159 Weighted fair queuing scheduler 4 2006
* 2007/0050,773 Weighted fair queuing scheduler 4 2006
 
ALCATEL CANADA INC. (2)
7289514 System and method for scheduling data traffic flows for a communication device 9 2002
* 2004/0100,967 System and method for scheduling data traffic flows for a communication device 12 2002
 
NEC CORPORATION (1)
* 6563791 Traffic shaping method and apparatus 1 1998
 
WSOU INVESTMENTS, LLC (7)
* 6075791 System for guaranteeing data transfer rates and delays in packet networks 68 1997
* 6529474 Shaping algorithm 6 1999
* 6434155 Weighted round robin engine used in scheduling the distribution of ATM cells 42 1999
* 6430152 Scheduler system for scheduling the distribution of ATM cells 15 1999
7664115 Method and apparatus for merging virtual connections 3 2000
* 8045549 Method and apparatus for packet reordering in a network processor 0 2003
* 2003/0189,931 Method and apparatus for packet reordering in a network processor 2 2003
 
APPLE INC. (2)
* 2012/0008,573 RADIO RESOURCE SIGNALING DURING NETWORK CONGESTION IN A MOBILE WIRELESS DEVICE 8 2010
9681450 Radio resource signaling during network congestion in a mobile wireless device 0 2012
 
JPMORGAN CHASE BANK, N.A. (1)
* 2006/0271,704 Approach to minimize worst-case queueing delay for a switching communication system with transmission constraints 0 2006
 
AVAYA INC. (2)
* 7831970 Method and apparatus for scheduling periodic tasks based on synthetic homogenization 1 2005
* 2007/0006,229 Method and apparatus for scheduling periodic tasks based on synthetic homogenization 6 2005
 
TELLABS OPERATIONS, INC. (5)
6987732 Apparatus and methods for scheduling packets in a broadband data stream 28 2000
* 2002/0110,134 Apparatus and methods for scheduling packets in a broadband data stream 23 2000
7697430 Apparatus and methods for scheduling packets in a broadband data stream 3 2005
* 2009/0086,628 Apparatus and methods for scheduling packets in a broadband data stream 6 2005
* 2007/0237,074 Configuration of congestion thresholds for a network traffic management system 14 2006
 
HUGHES NETWORK SYSTEMS, LLC (1)
* 7370116 Approach to minimize worst-case queuing delay for a switching communication system with transmission constraints 29 2006
 
GOOGLE TECHNOLOGY HOLDINGS LLC (3)
7310345 Empty indicators for weighted fair queues 3 2001
7280474 Weighted fair queue having adjustable scaling factor 2 2001
* 2003/0081,552 Weighted fair queue having adjustable scaling factor 0 2001
 
SYNETIC SYSTEMS LIMITED (1)
* 2004/0258,149 System and method for storing audio/video data 11 2004
 
ELECTRONICS AND TELECOMMUNICATIONS RESEARCH INSTITUTE (3)
* 7835290 Method for measuring end-to-end delay in asynchronous packet transfer network, and asynchronous packet transmitter and receiver 5 2006
* 2007/0097,865 Method for measuring end-to-end delay in asynchronous packet transfer network, and asynchronous packet transmitter and receiver 9 2006
* 2010/0040,090 SYNCHRONIZATION METHOD FOR ALLOWING FIXED TIME DELAY AND BRIDGE EMPLOYING THE SAME 4 2009
 
NOKIA TELECOMMUNICATIONS OY (1)
* 6081843 System using simulation cell and simulation buffer for regulating cell transfer rate according to occupancy level of the simulation buffer 37 1997
 
MICRO FOCUS SOFTWARE INC. (1)
* 6816903 Directory enabled policy management tool for intelligent traffic management 143 1999
 
INTERNATIONAL BUSINESS MACHINES CORPORATION (30)
7315901 Method and system for network processor scheduling outputs using disconnect/reconnect flow queues 3 2000
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
6804249 Method and system for network processor scheduling based on calculation 18 2000
6795870 Method and system for network processor scheduler 36 2000
7317683 Weighted fair queue serving plural output ports 5 2001
7187684 Weighted fair queue having extended effective range 7 2001
7103051 QoS scheduler and method for implementing quality of service with aging time stamps 4 2001
* 7046676 QoS scheduler and method for implementing quality of service with cached status array 15 2001
6982986 QoS scheduler and method for implementing quality of service anticipating the end of a chain of flows 8 2001
6973036 QoS scheduler and method for implementing peak service distance using next peak service time violated indication 9 2001
* 2003/0081,611 QoS scheduler and method for implementing quality of service with aging time stamps 2 2001
* 2003/0081,544 QoS scheduler and method for implementing quality of service with cached status array 2 2001
* 2003/0081,549 Weighted fair queue serving plural output ports 2 2001
* 2003/0081,612 QoS scheduler and method for implementing quality of service anticipating the end of a chain of flows 5 2001
* 2003/0081,543 QoS scheduler and method for implementing peak service distance using next peak service time violated indication 0 2001
7680043 Network processor having fast flow queue disable process 1 2002
7257124 Method and apparatus for improving the fairness of new attaches to a weighted fair queue in a quality of service (QoS) scheduler 4 2002
* 2003/0179,765 Method and apparatus for improving the fairness of new attaches to a weighted fair queue in a quality of service (QoS) scheduler 0 2002
7385997 Priority based bandwidth allocation within real-time and non-real-time traffic streams 112 2002
* 2003/0189,943 Priority based bandwidth allocation within real-time and non-real-time traffic streams 59 2002
7872968 Priority based bandwidth allocation within real-time and non-real time traffic streams 0 2006
8243597 Application layer synchronous traffic shaping 2 2007
* 2008/0212,470 METHOD FOR APPLICATION LAYER SYNCHRONOUS TRAFFIC SHAPING 149 2007
* 8223640 Synchronous traffic shaping 0 2007
* 2008/0212,474 METHOD FOR SYNCHRONOUS TRAFFIC SHAPING 1 2007
* 2009/0055,234 SYSTEM AND METHODS FOR SCHEDULING MEETINGS BY MATCHING A MEETING PROFILE WITH VIRTUAL RESOURCES 14 2007
7929548 Weighted fair queue serving plural output ports 1 2008
7899069 Priority based bandwidth allocation within real-time and non-real-time traffic streams 0 2008
* 2008/0232,386 PRIORITY BASED BANDWIDTH ALLOCATION WITHIN REAL-TIME AND NON-REAL-TIME TRAFFIC STREAMS 23 2008
 
ERICSSON AB (2)
* 6331970 Dynamic generic cell rate algorithm for policing ABR traffic 11 1998
* 7418523 Operation of a multiplicity of time sorted queues with reduced memory 15 2002
 
ALTERWAN, INC. (4)
8595478 Wide area network with high quality of service 2 2007
9015471 Inter-autonomous networking involving multiple service providers 2 2013
9525620 Private tunnel usage to create wide area network backbone over the internet 0 2015
9667534 VPN usage to create wide area network backbone over the internet 0 2015
 
EXTREME NETWORKS, INC. (2)
* 6654374 Method and apparatus to reduce Jitter in packet switched networks 40 1998
* 7602721 Methods and systems for fine grain bandwidth allocation in a switched network element 10 2003
 
CISCO TECHNOLOGY, INC. (2)
* 8305896 Selective performance enhancement of traffic flows 2 2007
* 2009/0109,849 SELECTIVE PERFORMANCE ENHANCEMENT OF TRAFFIC FLOWS 37 2007
 
GLOBALFOUNDRIES INC. (1)
6438135 Dynamic weighted round robin queuing 53 1999
 
Network Equipment Technologies, Inc. (1)
6717912 Fair discard system 17 2000
 
ADTRAN, INC. (2)
* 7006440 Aggregate fair queuing technique in a communications system using a class based queuing architecture 26 2001
* 2003/0081,546 Aggregate fair queuing technique in a communications system using a class based queuing architecture 27 2001
 
SOUND VIEW INNOVATIONS, LLC (1)
* 2003/0112,748 System and method for detecting failures and re-routing connections in a communication network 74 2001
 
UNIVERSITY OF PITTSBURGH - OF THE COMMONWEALTH SYSTEM OF HIGHER EDUCATION (1)
* 2002/0133,325 Discrete event simulator 52 2002
 
WORLD WIDE PACKETS, INC. (3)
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
7269180 System and method for prioritizing and queuing traffic 5 2002
 
AT&T INTELLECTUAL PROPERTY II, L.P. (2)
6839768 Startup management system and method for rate-based flow and congestion control within a network 52 2000
* 2004/0246,897 Startup management system and method for networks 18 2004
 
RPX CLEARINGHOUSE LLC (2)
* 6279035 Optimizing flow detection and reducing control plane processing in a multi-protocol over ATM (MPOA) system 73 1998
* 6646986 Scheduling of variable sized packet data under transfer rate control 25 1999
 
ARRIS ENTERPRISES LLC (1)
8689260 Method and apparatus for scheduling broadcast information 0 2012
 
UNIVERSITY OF MARYLAND, BALTIMORE (1)
* 2007/0058,564 Method and device for managing data flow in a synchronous network 4 2006
 
FORCE10 NETWORKS, INC. (1)
* 6714554 Method and system for sorting packets in a network 9 2001
 
INTEL CORPORATION (8)
* 2002/0036,984 Method and apparatus for guaranteeing data transfer rates and enforcing conformance with traffic profiles in a packet network 54 2001
7586909 Striping algorithm for switching fabric 25 2002
7319695 Deficit-based striping algorithm 21 2002
7426185 Backpressure mechanism for switching fabric 28 2003
7480246 Characterizing transmission of data segments within a switch fabric using multiple counters for each destination node 14 2007
* 2007/0189,283 CHARACTERIZING TRANSMISSION OF DATA SEGMENTS WITHIN A SWITCH FABRIC USING MULTIPLE COUNTERS FOR EACH DESTINATION NODE 42 2007
7983287 Backpressure mechanism for switching fabric 3 2008
* 2008/0212,472 BACKPRESSURE MECHANISM FOR SWITCHING FABRIC 57 2008
 
RPX CORPORATION (4)
7680897 Methods and systems for managing network traffic 148 2003
7349337 Techniques for shaping data transmission rates 31 2003
* 8259738 Channel service manager with priority queuing 8 2007
* 2008/0273,545 Channel service manager with priority queuing 11 2007
 
SYNAPTICS INCORPORATED (2)
* 7643413 System and method for providing quality of service in asynchronous transfer mode cell transmission 0 2003
* 2004/0184,460 System and method for providing quality of service in asynchronous transfer mode cell transmission 1 2003
 
TEXAS INSTRUMENTS INCORPORATED (2)
* 6205151 ATM cell scheduler which uses a heap memory and associates timestamps with each channel 95 1997
* 6115360 Fair scheduling of ATM cell transmissions during overscheduled conditions 93 1997
 
Celox Networks, Inc. (1)
6810031 Method and device for distributing bandwidth 33 2000
 
MATSUSHITA ELECTRIC INDUSTRIAL CO., LTD. (1)
* 6590865 Transmission system, bandwidth management apparatus, and bandwidth management method 56 1999
 
AT&T CORP. (1)
* 6192406 Startup management system and method for networks 24 1997
* Cited By Examiner