[go: up one dir, main page]

Wang et al., 2009 - Google Patents

Succinct priority indexing structures for the management of large priority queues

Wang et al., 2009

View PDF
Document ID
2592972963401020850
Author
Wang H
Lin B
Publication year
Publication venue
2009 17th International Workshop on Quality of Service

External Links

Snippet

Priority queues are an essential building block for implementing advanced per-flow service disciplines at high-speed network links. In this paper, we propose novel solutions to the scalable implementation of priority queues by decomposing the problem into two parts, a …
Continue reading at citeseerx.ist.psu.edu (PDF) (other versions)

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for programme control, e.g. control unit
    • G06F9/06—Arrangements for programme control, e.g. control unit using stored programme, i.e. using internal store of processing equipment to receive and retain programme
    • G06F9/46—Multiprogramming arrangements
    • G06F9/48—Programme initiating; Programme switching, e.g. by interrupt
    • G06F9/4806—Task transfer initiation or dispatching
    • G06F9/4843—Task transfer initiation or dispatching by program, e.g. task dispatcher, supervisor, operating system
    • G06F9/4881—Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for programme control, e.g. control unit
    • G06F9/06—Arrangements for programme control, e.g. control unit using stored programme, i.e. using internal store of processing equipment to receive and retain programme
    • G06F9/46—Multiprogramming arrangements
    • G06F9/54—Interprogramme communication; Intertask communication
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/54—Store-and-forward switching systems
    • H04L12/56—Packet switching systems
    • H04L12/5693—Queue scheduling in packet switching networks
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30946—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30286—Information retrieval; Database structures therefor; File system structures therefor in structured data stores
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic regulation in packet switching networks
    • H04L47/10—Flow control or congestion control
    • H04L47/24—Flow control or congestion control depending on the type of traffic, e.g. priority or quality of service [QoS]
    • H04L47/2441—Flow classification
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F5/00—Methods or arrangements for data conversion without changing the order or content of the data handled
    • G06F5/06—Methods or arrangements for data conversion without changing the order or content of the data handled for changing the speed of data flow, i.e. speed regularising or timing, e.g. delay lines, FIFO buffers; over- or underrun control therefor
    • G06F5/10—Methods or arrangements for data conversion without changing the order or content of the data handled for changing the speed of data flow, i.e. speed regularising or timing, e.g. delay lines, FIFO buffers; over- or underrun control therefor having a sequence of storage locations each being individually accessible for both enqueue and dequeue operations, e.g. using random access memory
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L49/00—Packet switching elements
    • H04L49/90—Queuing arrangements
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F15/00—Digital computers in general; Data processing equipment in general
    • G06F15/76—Architectures of general purpose stored programme computers
    • G06F15/78—Architectures of general purpose stored programme computers comprising a single central processing unit
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F15/00—Digital computers in general; Data processing equipment in general
    • G06F15/16—Combinations of two or more digital computers each having at least an arithmetic unit, a programme unit and a register, e.g. for a simultaneous processing of several programmes

Similar Documents

Publication Publication Date Title
Saeed et al. Eiffel: Efficient and flexible software packet scheduling
US7310348B2 (en) Network processor architecture
US7876763B2 (en) Pipeline scheduler including a hierarchy of schedulers and multiple scheduling lanes
CN1736068B (en) Flow management structure system
US8537832B2 (en) Exception detection and thread rescheduling in a multi-core, multi-thread network processor
US7006505B1 (en) Memory management system and algorithm for network processor architecture
US7457296B2 (en) Method and apparatus for sorting packets in packet schedulers using a connected trie data structure
US7529224B2 (en) Scheduler, network processor, and methods for weighted best effort scheduling
Xie et al. Pandas: robust locality-aware scheduling with stochastic delay optimality
Wang et al. Succinct priority indexing structures for the management of large priority queues
US11552907B2 (en) Efficient packet queueing for computer networks
US7460544B2 (en) Flexible mesh structure for hierarchical scheduling
WO2003090018A2 (en) Network processor architecture
Wang et al. Per-flow queue management with succinct priority indexing structures for high speed packet scheduling
WO2003088047A1 (en) System and method for memory management within a network processor architecture
US7474662B2 (en) Systems and methods for rate-limited weighted best effort scheduling
Wang et al. DRAM-based statistics counter array architecture with performance guarantee
Kogan et al. Towards software-defined buffer management
Wang et al. Design and analysis of a robust pipelined memory system
Shi et al. On the extreme parallelism inside next-generation network processors
Wang et al. Block-based packet buffer with deterministic packet departures
Lin et al. Integration of scheduling real-time traffic and cell loss control for ATM networks
Bhagwan et al. Design of a high-speed packet switch with fine-grained quality-of-service guarantees
Wang et al. Per-flow queue scheduling with pipelined counting priority index
Kumar et al. A scalable, cache-based queue management subsystem for network processors