Per-flow dynamic buffer management

Number of patents in Portfolio can not be more than 2000

United States of America Patent

PATENT NO 6515963
SERIAL NO

09238552

Stats

ATTORNEY / AGENT: (SPONSORED)

Importance

Loading Importance Indicators... loading....

Abstract

See full text

The present invention provides a per-flow dynamic buffer management scheme for a data communications device. With per-flow dynamic buffer limiting, the header information for each packet is mapped into an entry in a flow table, with a separate flow table provided for each output queue. Each flow table entry maintains a buffer count for the packets currently in the queue for each flow. On each packet enqueuing action, a dynamic buffer limit is computed for the flow and compared against the buffer count already used by the flow to make a mark, drop, or enqueue decision. A packet in a flow is dropped or marked if the buffer count is above the limit. Otherwise, the packet is enqueued and the buffer count incremented by the amount used by the newly-enqueued packet. The scheme operates independently of packet data rate and flow behavior, providing means for rapidly discriminating well-behaved flows from non-well-behaved flows in order to manage buffer allocation accordingly. Additionally, the present invention adapts to changing flow requirements by fairly sharing buffer resources among both well-behaved and non-well-behaved flows.

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

First Claim

See full text

Family

Loading Family data... loading....

Patent Owner(s)

Patent OwnerAddressTotal Patents
CISCO TECHNOLOGY, INC.SAN JOSE, CA14366

International Classification(s)

  • [Classification Symbol]
  • [Patents Count]

Inventor(s)

Inventor Name Address # of filed Patents Total Citations
Bechtolsheim, Andreas V Stanford, CA 27 1513
Cheriton, David R Palo Alto, CA 77 1858

Cited Art Landscape

Patent Info (Count) # Cites Year
 
INTERNATIONAL BUSINESS MACHINES CORPORATION (2)
* 5875442 Method and apparatus for enhancing access to a remote database employing dynamic buffer management 6 1992
* 6263333 Method for searching non-tokenized text and tokenized text for matches against a keyword data structure 28 1998
 
MASSACHUSETTS INSTITUTE OF TECHNOLOGY (1)
* 5530958 Cache memory system and method with multiple hashing functions and hash control storage 104 1994
 
MAXTOR CORPORATION (1)
* 5963977 Buffer management and system coordination method 7 1997
 
CISCO TECHNOLOGY, INC. (5)
5088032 Method and apparatus for routing communications among computer networks 366 1988
5224099 Circuitry and method for fair queuing and servicing cell traffic using hopcounts and traffic classes 184 1991
5359592 Bandwidth and congestion control for queue channels in a cell switching communication controller 175 1993
5473607 Packet filtering for data networks 343 1993
5561663 Method and apparatus for performing communication rate control using geometric weighted groups 63 1994
 
NEMES, RICHARD M. (1)
* 5893120 Methods and apparatus for information storage and retrieval using a hashing technique with external chaining and on-the-fly removal of expired data 57 1997
 
AVAGO TECHNOLOGIES GENERAL IP (SINGAPORE) PTE. LTD. (2)
5708659 Method for hashing in a packet network switching system 202 1995
* 6094712 Computer network interface for direct mapping of data transferred between applications on different host computers from virtual addresses to physical memory addresses application data 32 1996
* Cited By Examiner

Patent Citation Ranking

Forward Cite Landscape

Patent Info (Count) # Cites Year
 
PMC-SIERRA, INC. (1)
* 2002/0107,974 Data traffic manager 12 2001
 
Other [Check patent profile for assignment information] (2)
* 2007/0268,841 METHODS AND SYSTEMS FOR CONFIGURING VOICE OVER INTERNET PROTOCOL NETWORK QUALITY OF SERVICE 13 2007
* 2008/0107,118 WEIGHTED FAIR QUEUE SERVING PLURAL OUTPUT PORTS 2 2008
 
ORCKIT IP, LLC (1)
* 6785232 Rate control in transmission of packet data over an ATM network 34 2000
 
EMC IP HOLDING COMPANY LLC (1)
* 7751407 Setting a ceiling for bandwidth used by background tasks in a shared port environment 2 2006
 
MARVELL ISRAEL (M.I.S.L.) LTD. (1)
* 8577854 Apparatus and method for high speed flow classification 1 2002
 
SAMSUNG ELECTRONICS CO., LTD. (2)
7636308 Controlling packet congestion 2 2005
* 2005/0195,740 Controlling packet congestion 16 2005
 
128 TECHNOLOGY, INC. (4)
9729439 Network packet flow controller 0 2014
9736184 Apparatus and method for using certificate data to route data 0 2015
9729682 Network device and method for processing a session using a packet signature 0 2015
9762485 Network packet flow controller with extended session management 0 2015
 
THE NASDAQ OMX GROUP, INC. (2)
* 2003/0236,946 Managed queues 3 2002
* 2003/0236,819 Queue-based data retrieval and transmission 8 2002
 
AT&T INTELLECTUAL PROPERTY I, L.P. (1)
* 2010/0039,959 METHODS, SYSTEMS, AND COMPUTER PROGRAM PRODUCTS FOR MANAGING ACCESS RESOURCES IN AN INTERNET PROTOCOL NETWORK 17 2009
 
AVAYA INC. (2)
7411971 Systems and methods for the schedule alignment of packet flow 2 2004
* 2005/0111,362 Systems and methods for the schedule alignment of a packet flow 20 2004
 
CELLCO PARTNERSHIP D/B/A VERIZON WIRELESS (1)
* 9071465 Method and system for SMS services and bind scaling 0 2010
 
Marvell Israel (M.I.S.L) Ltd. (2)
8176291 Buffer management architecture 0 2010
8661223 Buffer management architecture 0 2012
 
ESTREET VENTURE FUND I, LLC (1)
* 2002/0165,957 Intelligent dynamic route selection based on active probing of network operational characteristics 184 2001
 
INTERNATIONAL BUSINESS MACHINES CORPORATION (7)
* 7873991 Technique of defending against network flooding attacks using a connectionless protocol 3 2000
* 6862629 Method and system for dispatching socks traffic based on socks connection identified by source address, application address and application level protocol 5 2000
* 2007/0156,879 Considering remote end point performance to select a remote end point to use to transmit a task 3 2006
* 2008/0025,215 METHOD AND APPARATUS FOR IMPROVING THE FAIRNESS OF NEW ATTACHES TO A WEIGHTED FAIR QUEUE IN A QUALITY OF SERVICE (QoS) SCHEDULER 0 2007
7929548 Weighted fair queue serving plural output ports 1 2008
* 7869365 System and program storage device for controlling data packet flows by manipulating data packets according to an actual manipulation rate 1 2008
* 2008/0267,070 System and program storage device for controlling data packet flows by manipulating data packets according to an actual manipulation rate 13 2008
 
ADVANCED MICRO DEVICES, INC. (1)
* 6744776 Servicing priority traffic in multiport network switch 42 2000
 
EXTREME NETWORKS, INC. (8)
7649879 Pipelined packet processor 8 2004
* 2005/0226,242 Pipelined packet processor 30 2004
* 7894451 Method of providing virtual router functionality 4 2005
7889750 Method of extending default fixed number of processing cycles in pipelined packet processor architecture 2 2005
7822033 MAC address detection device for virtual routers 2 2005
* 7817633 Method of providing virtual router functionality through abstracted virtual identifiers 3 2005
* 2007/0153,808 Method of providing virtual router functionality 10 2005
8605732 Method of providing virtual router functionality 0 2011
 
CISCO TECHNOLOGY, INC. (21)
* 7324514 Implementing access control lists using a balanced hash table of access control list binary comparison trees 12 2000
* 6778495 Combining multilink and IP per-destination load balancing over a multilink bundle 80 2000
* 7149187 Random early detection policer using randomization of packet drops 20 2000
* 8145787 Adaptive bandwidth utilization over fabric links 3 2001
* 7602716 Load sharing on DOCSIS 1 2001
* 6829217 Per-flow dynamic buffer management 24 2002
8040886 Programmable packet classification system using an array of uniform content-addressable memories 2 2003
* 2004/0213,235 Programmable packet classification system using an array of uniform content-addressable memories 33 2003
7613110 Combining multilink and IP per-destination load balancing over a multilink bundle 21 2004
7215641 Per-flow dynamic buffer management 35 2004
* 7680806 Reducing overflow of hash table entries 2 2005
* 2006/0265,370 Method and apparatus for reducing overflow of hash table entries 6 2005
7948883 Applying router quality of service on a cable modem interface on a per-service-flow basis 13 2007
* 8305896 Selective performance enhancement of traffic flows 2 2007
* 2009/0109,849 SELECTIVE PERFORMANCE ENHANCEMENT OF TRAFFIC FLOWS 36 2007
8379524 Prioritization and preemption of data frames over a switching fabric 7 2008
7894342 Efficient pruning of virtual services in bridged computer networks 0 2009
* 2010/0220,730 EFFICIENT PRUNING OF VIRTUAL SERVICES IN BRIDGED COMPUTER NETWORKS 4 2009
8861358 Applying router quality of service on a cable modem interface on a per-service-flow basis 0 2011
* 2011/0194,411 APPLYING ROUTER QUALITY OF SERVICE ON A CABLE MODEM INTERFACE ON A PER-SERVICE-FLOW BASIS 4 2011
9094327 Prioritization and preemption of data frames over a switching fabric 0 2012
 
SIEMENS AKTIENGESELLSCHAFT (1)
* 2005/0254,487 Method communication system and communication device for transmitting information 0 2004
 
GLOBALFOUNDRIES INC. (1)
7107367 Method for efficient buffer tag allocation 10 2003
 
SAISEI NETWORKS PTE LTD (2)
8547843 System, method, and computer program product for controlling output port utilization 1 2006
* 2007/0171,826 System, method, and computer program product for controlling output port utilization 5 2006
 
FUJITSU LIMITED (4)
* 2002/0010,787 Network connecting device 2 2001
* 7391765 Congestion control system for VoIP network 4 2002
* 2003/0107,991 Congestion control system for VoIP network 9 2002
* 2008/0205,646 COMPUTER-READABLE RECORDING MEDIUM STORING DATA DECRYPTION PROGRAM, DATA DECRYPTION METHOD, AND DATA DECRYPTION DEVICE 0 2008
 
AT&T INTELLECTUAL PROPERTY II, L.P. (1)
7817624 Methods and systems for configuring voice over internet protocol network quality of service 3 2007
 
PROVENANCE ASSET GROUP LLC (2)
7349336 Random early drop with per hop behavior biasing 20 2003
* 2003/0223,362 Random early drop with per hop behavior biasing 4 2003
 
NOKIA INTERNET COMMUNICATIONS INC. (1)
* 7277388 Method and apparatus for random packet marking for differentiated services 9 2000
 
INTEL CORPORATION (5)
* 7039061 Methods and apparatus for retaining packet order in systems utilizing multiple transmit queues 35 2001
* 2003/0058,876 Methods and apparatus for retaining packet order in systems utilizing multiple transmit queues 7 2001
7248593 Method and apparatus for minimizing spinlocks and retaining packet order in systems utilizing multiple transmit queues 3 2002
* 2003/0058,878 Method and apparatus for minimizing spinlocks and retaining packet order in systems utilizing multiple transmit queues 14 2002
* 2003/0223,442 Buffer memory reservation 22 2002
 
TEXAS INSTRUMENTS INCORPORATED (1)
* 6970430 Method to measure throughput efficiency of low speed modem relay over packet network 6 2000
 
TELOGY NETWORKS, INC. (1)
* 2002/0085,501 Method to measure throughput efficiency of low speed modem relay over packet networks 6 2000
 
ISS MANUFACTURING LIMITED (1)
* 2008/0031,134 Method, device and software for controlling the data traffic between a first computer network and a second computer network 0 2006
 
NORTEL NETWORKS LIMITED (1)
* 2002/0133,617 Allocating traffic between a plurality of paths in a communications network 4 2001
 
HEWLETT PACKARD ENTERPRISE DEVELOPMENT LP (14)
* 7213087 Mechanism to control the allocation of an N-source shared buffer 27 2000
* 6765922 Speculative transmit for system area network latency reduction 3 2000
* 7032222 Method and system for determining resource allocation to users by granting request based on user associated different limits and resource limit 30 2000
* 7333498 Method and apparatus for separating data packets in a memory buffer 1 2002
* 7894480 Computer system and network interface with hardware based rule checking for embedded firewall 11 2002
* 7724740 Computer system and network interface supporting class of service queues 22 2002
* 6882656 Speculative transmit for system area network latency reduction 2 2004
* 2004/0190,538 Speculative transmit for system area network latency reduction 45 2004
7697519 Packet processing 6 2006
* 2008/0101,354 Packet processing 16 2006
* 9479464 Computer system and network interface with hardware based packet filtering and classification 3 2009
8358655 Computer system and network interface supporting class of service queues 4 2010
* 2010/0191,865 COMPUTER SYSTEM AND NETWORK INTERFACESUPPORTING CLASS OF SERVICE QUEUES 2 2010
9348789 Computer system and network interface supporting class of service queues 0 2012
 
JUNIPER NETWORKS, INC. (4)
* 8879395 Filtering and route lookup in a switching device 2 2013
* 2013/0308,644 FILTERING AND ROUTE LOOKUP IN A SWITCHING DEVICE 8 2013
9258228 Filtering and route lookup in a switching device 0 2014
9813339 Filtering and route lookup in a switching device 0 2015
 
MARVELL ISRAEL (MISL) LTD. (1)
7689793 Buffer management architecture 0 2004
 
NEC CORPORATION (6)
* 7327671 Method and system for controlling communication network and router used in the network 15 2002
* 2003/0022,619 Method and system for controlling communication network and router used in the network 0 2002
8446828 Method and system for controlling communication network and router used in the network 0 2007
* 2007/0189,213 Method and system for controlling communication network and router used in the network 14 2007
7843920 Method and system for controlling communication network and router used in the network 13 2007
* 2007/0263,627 Method and system for controlling communication network and router used in the network 18 2007
 
WSOU INVESTMENTS, LLC (2)
* 7039056 High quality audio and video over digital subscriber lines (DSLs) 1 2001
* 2003/0026,265 High quality audio and video over digital subscriber lines (DSLs) 0 2001
 
SEAGATE TECHNOLOGY LLC (3)
* 6993604 Dynamic buffer size allocation for multiplexed streaming 14 2001
* 2002/0087,758 Dynamic buffer size allocation for multiplexed streaming 2 2001
* 2006/0080,482 Dynamic buffer size allocation for multiplexed streaming 2 2005
 
AVAGO TECHNOLOGIES GENERAL IP (SINGAPORE) PTE. LTD. (3)
* 7120117 Starvation free flow control in a shared memory switching device 13 2000
* 6990073 Data packet congestion management technique 14 2001
8411574 Starvation free flow control in a shared memory switching device 5 2006
 
CREDIT SUISSE AG (1)
* 2013/0034,101 Programmable Packet Processor With Flow Resolution Logic 0 2012
 
QUALCOMM INCORPORATED (1)
* 6807426 Method and apparatus for scheduling transmissions in a communication system 66 2001
 
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
 
THE BOARD OF TRUSTEES OF THE LELAND STANFORD JUNIOR UNIVERSITY (1)
* 7324442 Active queue management toward fair bandwidth allocation 21 2001
 
ALCATEL LUCENT (1)
* 8724632 Programmable packet processor with flow resolution logic 0 2012
 
TELEFONAKTIEBOLAGET L M ERICSSON (PUBL) (1)
* 2014/0105,218 QUEUE MONITORING TO FILTER THE TREND FOR ENHANCED BUFFER MANAGEMENT AND DYNAMIC QUEUE THRESHOLD IN 4G IP NETWORK/EQUIPMENT FOR BETTER TRAFFIC PERFORMANCE 8 2012
 
CIENA CORPORATION (1)
* 6765871 Fiber channel flow control method and apparatus for interface to metro area transport link 34 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
 
ERICSSON INC. (1)
* 6738371 Ingress data queue management in a packet data router 113 1999
 
RPX CLEARINGHOUSE LLC (4)
* 8819265 Managing flow control buffer 0 2003
* 2005/0138,243 Managing flow control buffer 48 2003
* 7394808 Method and apparatus for implementing scheduling algorithms in a network element 5 2004
* 2005/0259,574 Method and apparatus for implementing scheduling algorithms in a network element 12 2004
 
SANDISK TECHNOLOGIES LLC (2)
* 8949491 Buffer memory reservation techniques for use with a NAND flash memory 0 2013
* 2015/0019,766 BUFFER MEMORY RESERVATION TECHNIQUES FOR USE WITH A NAND FLASH MEMORY 0 2013
 
BROCADE COMMUNICATIONS SYSTEMS, INC. (2)
8824294 Source-based congestion detection and control 4 2011
* 2011/0235,518 SOURCE-BASED CONGESTION DETECTION AND CONTROL 4 2011
 
NETWORK APPLIANCE, INC. (1)
* 7469295 Modified round robin load balancing technique based on IP identifier 11 2001
 
AT&T CORP. (1)
7251216 Methods and systems for configuring voice over internet protocol network quality of service 11 2003
* Cited By Examiner