[go: up one dir, main page]

Lenzini et al., 2004 - Google Patents

Tradeoffs between low complexity, low latency, and fairness with deficit round-robin schedulers

Lenzini et al., 2004

View PDF
Document ID
17061183593362954411
Author
Lenzini L
Mingozzi E
Stea G
Publication year
Publication venue
IEEE/ACM Transactions on Networking

External Links

Snippet

Deficit Round-Robin (DRR) is a scheduling algorithm devised for providing fair queueing in the presence of variable length packets. The main attractive feature of DRR is its simplicity of implementation: in fact, it can exhibit O (1) complexity, provided that specific allocation …
Continue reading at profesores.fi-b.unam.mx (PDF) (other versions)

Classifications

    • 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
    • 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/5601—Transfer mode dependent, e.g. ATM
    • H04L2012/5678—Traffic aspects, e.g. arbitration, load balancing, smoothing, buffer management
    • H04L2012/5679—Arbitration or scheduling
    • 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/5601—Transfer mode dependent, e.g. ATM
    • H04L2012/5638—Services, e.g. multimedia, GOS, QOS
    • H04L2012/5646—Cell characteristics, e.g. loss, delay, jitter, sequence integrity
    • 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
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic regulation in packet switching networks
    • H04L47/50—Queue scheduling
    • H04L47/62—General aspects
    • H04L47/6215—Individual queue per QOS, rate or priority
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic regulation in packet switching networks
    • H04L47/50—Queue scheduling
    • H04L47/62—General aspects
    • H04L47/622—Queue service order
    • H04L47/623—Queue service order weighted service order
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic regulation in packet switching networks
    • H04L47/50—Queue scheduling
    • H04L47/56—Delay aware scheduling
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L49/00—Packet switching elements
    • H04L49/25—Routing or path finding through a switch fabric
    • H04L49/253—Connections establishment or release between ports
    • H04L49/254—Centralized controller, i.e. arbitration or scheduling
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/64—Hybrid switching systems
    • H04L12/6402—Hybrid switching fabrics
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/28—Data switching networks characterised by path configuration, e.g. local area networks [LAN], wide area networks [WAN]
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L49/00—Packet switching elements
    • H04L49/90—Queuing arrangements
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/02—Details
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L43/00—Arrangements for monitoring or testing packet switching networks
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATIONS NETWORKS
    • H04W72/00—Local resource management, e.g. wireless traffic scheduling or selection or allocation of wireless resources
    • H04W72/12—Dynamic Wireless traffic scheduling; Dynamically scheduled allocation on shared channel
    • H04W72/1205—Schedule definition, set-up or creation
    • H04W72/1221—Schedule definition, set-up or creation based on age of data to be sent

Similar Documents

Publication Publication Date Title
Lenzini et al. Tradeoffs between low complexity, low latency, and fairness with deficit round-robin schedulers
Marsan et al. Packet-mode scheduling in input-queued cell-based switches
Stiliadis et al. Efficient fair queueing algorithms for packet-switched networks
US7876763B2 (en) Pipeline scheduler including a hierarchy of schedulers and multiple scheduling lanes
US8325736B2 (en) Propagation of minimum guaranteed scheduling rates among scheduling layers in a hierarchical schedule
Tsao et al. Pre-order deficit round robin: a new scheduling algorithm for packet-switched networks
Chen et al. Performance study of an input queueing packet switch with two priority classes
Lenzini et al. Aliquem: a novel DRR implementation to achieve better latency and fairness at O (1) complexity
Guo SRR: An O (1) time-complexity packet scheduler for flows in multiservice packet networks
Ramabhadran et al. The stratified round robin scheduler: design, analysis and implementation
Matsufuru et al. Efficient fair queueing for ATM networks using uniform round robin
US7599381B2 (en) Scheduling eligible entries using an approximated finish delay identified for an entry based on an associated speed group
Dwekat et al. A practical fair queuing scheduler: Simplification through quantization
Lenzini et al. Full exploitation of the deficit round Robin capabilities by efficient implementation and parameter tuning
Tong et al. Quantum varying deficit round robin scheduling over priority queues
Lenzini et al. Performance analysis of modified deficit round robin schedulers
Sun et al. Coordinated aggregate scheduling for improving end-to-end delay performance
Lenzini et al. Eligibility-based round robin for fair and efficient packet scheduling in wormhole switching networks
Maertens et al. Effect of class clustering on delay differentiation in priority scheduling
Hu et al. Dynamic queuing sharing mechanism for per-flow quality of service control
Liang A simple and effective scheduling mechanism using minimized cycle round robin
Kwak et al. A new starting potential fair queuing algorithm with O (1) virtual time computation complexity
Tsou et al. Design and simulation of an efficient real-time traffic scheduler with jitter and delay guarantees
Rouskas et al. A practical and efficient implementation of WF 2 Q+
EP1774721B1 (en) Propagation of minimum guaranteed scheduling rates