|
Deficit Weighted Round Robin
Deficit Round Robin (DRR), also Deficit Weighted Round Robin (DWRR), is a scheduling algorithm for the network scheduler. DRR is, similar to weighted fair queuing (WFQ), a packet-based implementation of the ideal Generalized Processor Sharing (GPS) policy. It was proposed by M. Shreedhar and G. Varghese in 1995 as an efficient (with ''O(1)'' complexity) and fair algorithm. Details In DRR, a scheduler handling N flows is configured with one quantum Q_i for each flow. This global idea is that, at each round, the flow i can send at most Q_i bytes, and the remaining, if any, is reported to the next round. In this way, the minimum rate that flow i will achieve over a long term is \fracR; where R is the link rate. Algorithm The DRR scans all non-empty queues in sequence. When a non-empty queue i is selected, its deficit counter is incremented by its quantum value. Then, the value of the deficit counter is a maximal number of bytes that can be sent at this turn: if the deficit counte ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Network Scheduler
A network scheduler, also called packet scheduler, queueing discipline (qdisc) or queueing algorithm, is an arbiter on a node in a packet switching communication network. It manages the sequence of network packets in the transmit and receive queues of the protocol stack and network interface controller. There are several network schedulers available for the different operating systems, that implement many of the existing network scheduling algorithms. The network scheduler logic decides which network packet to forward next. The network scheduler is associated with a queuing system, storing the network packets temporarily until they are transmitted. Systems may have a single or multiple queues in which case each may hold the packets of one flow, classification, or priority. In some cases it may not be possible to schedule all transmissions within the constraints of the system. In these cases the network scheduler is responsible for deciding which traffic to forward and what ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Weighted Fair Queuing
Weighted fair queueing (WFQ) is a network scheduling algorithm. WFQ is both a packet-based implementation of the generalized processor sharing (GPS) policy, and a natural extension of fair queuing (FQ). Whereas FQ shares the link's capacity in equal subparts, WFQ allows schedulers to specify, for each flow, which fraction of the capacity will be given. Weighted fair queuing is also known as packet-by-packet GPS (PGPS or P-GPS) since it approximates generalized processor sharing "to within one packet transmission time, regardless of the arrival patterns." Parametrization and fairness Like other GPS-like scheduling algorithms, the choice of the weights is left to the network administrator. There is no unique definition of what is "fair" (see for further discussion). By regulating the WFQ weights dynamically, WFQ can be utilized for controlling the quality of service Quality of service (QoS) is the description or measurement of the overall performance of a service, such ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Generalized Processor Sharing
Generalized processor sharing (GPS) is an ideal scheduling algorithm for process schedulers and network schedulers. It is related to the fair-queuing principle which groups packets into classes and shares the service capacity between them. GPS shares this capacity ''according to some fixed weights''. In process scheduling, GPS is "an idealized scheduling algorithm that achieves perfect fairness. All practical schedulers approximate GPS and use it as a reference to measure fairness." Generalized processor sharing assumes that traffic is fluid (infinitesimal packet sizes), and can be arbitrarily split. There are several service disciplines which track the performance of GPS quite closely such as weighted fair queuing (WFQ), also known as packet-by-packet generalized processor sharing (PGPS). Justification In a network such as the internet, different application types require different levels of performance. For example, email is a genuinely store and forward kind of application, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
George Varghese
George Varghese (born 1960) is a computer scientist, a professor of computer science and Jonathan B. Postel Chair in Networking in the UCLA Henry Samueli School of Engineering and Applied Science. He is the author of the textbook ''Network Algorithmics,'' published by Morgan Kaufmann in 2004. Education and career Varghese received his B.Tech in electrical engineering from IIT Bombay in 1981, his M.S. in computer studies from NCSU in 1983 and his Ph.D. in computer science from MIT in 1993, where his advisor was Nancy Lynch. He has been a Fellow of the ACM since 2002. Varghese was a professor at Washington University in St. Louis from 1992 until 1999, when he moved to the University of California, San Diego. He worked at Microsoft Research from 2012 until 2016, and took his present position at the University of California, Los Angeles in 2016. Research Transparent Bridge Architecture Before his Ph.D., George spent several years as part of the network architecture and adva ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Traffic Flow (computer Networking)
In packet switching networks, traffic flow, packet flow or ''network flow'' is a sequence of packets from a source computer to a destination, which may be another host, a multicast group, or a broadcast domain. RFC 2722 defines traffic flow as "an artificial logical equivalent to a call or connection." RFC 3697 defines traffic flow as "a sequence of packets sent from a particular source to a particular unicast, anycast, or multicast destination that the source desires to label as a flow. A flow could consist of all packets in a specific transport connection or a media stream. However, a flow is not necessarily 1:1 mapped to a transport connection." Flow is also defined in RFC 3917 as "a set of IP packets passing an observation point in the network during a certain time interval." Packet flow temporal efficiency can be affected by one-way delay (OWD) that is described as a combination of the following components: * Processing delay (the time taken to process a packet in a netw ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Linux Kernel
The Linux kernel is a Free and open-source software, free and open source Unix-like kernel (operating system), kernel that is used in many computer systems worldwide. The kernel was created by Linus Torvalds in 1991 and was soon adopted as the kernel for the GNU operating system (OS) which was created to be a free software, free replacement for Unix. Since the late 1990s, it has been included in many Linux distributions, operating system distributions, many of which are called Linux. One such Linux kernel operating system is Android (operating system), Android which is used in many mobile and embedded devices. Most of the kernel code is written in C (programming language), C as supported by the GNU compiler collection (GCC) which has extensions beyond standard C. The code also contains assembly language, assembly code for architecture-specific logic such as optimizing memory use and task execution. The kernel has a Modular programming, modular design such that modules can be inte ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Kernel
Kernel may refer to: Computing * Kernel (operating system), the central component of most operating systems * Kernel (image processing), a matrix used for image convolution * Compute kernel, in GPGPU programming * Kernel method, in machine learning * Kernelization, a technique for designing efficient algorithms ** Kernel, a routine that is executed in a vectorized loop, for example in general-purpose computing on graphics processing units *KERNAL, the Commodore operating system Mathematics Objects * Kernel (algebra), a general concept that includes: ** Kernel (linear algebra) or null space, a set of vectors mapped to the zero vector ** Kernel (category theory), a generalization of the kernel of a homomorphism ** Kernel (set theory), an equivalence relation: partition by image under a function ** Difference kernel, a binary equalizer: the kernel of the difference of two functions Functions * Kernel (geometry), the set of points within a polygon from which the whole polygon boundary ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
GNU General Public License
The GNU General Public Licenses (GNU GPL or simply GPL) are a series of widely used free software licenses, or ''copyleft'' licenses, that guarantee end users the freedom to run, study, share, or modify the software. The GPL was the first copyleft license available for general use. It was originally written by Richard Stallman, the founder of the Free Software Foundation (FSF), for the GNU Project. The license grants the recipients of a computer program the rights of the Free Software Definition. The licenses in the GPL series are all copyleft licenses, which means that any derivative work must be distributed under the same or equivalent license terms. The GPL is more restrictive than the GNU Lesser General Public License, and even more distinct from the more widely used permissive software licenses such as BSD, MIT, and Apache. Historically, the GPL license family has been one of the most popular software licenses in the free and open-source software (FOSS) domai ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Scheduling Algorithm
In computing, scheduling is the action of assigning resources to perform tasks. The resources may be processors, network links or expansion cards. The tasks may be threads, processes or data flows. The scheduling activity is carried out by a mechanism called a scheduler. Schedulers are often designed so as to keep all computer resources busy (as in load balancing), allow multiple users to share system resources effectively, or to achieve a target quality-of-service. Scheduling is fundamental to computation itself, and an intrinsic part of the execution model of a computer system; the concept of scheduling makes it possible to have computer multitasking with a single central processing unit (CPU). Goals A scheduler may aim at one or more goals, for example: * maximizing ''throughput'' (the total amount of work completed per time unit); * minimizing '' wait time'' (time from work becoming ready until the first point it begins execution); * minimizing '' latency'' or '' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Fair Queuing
Fair queuing is a family of scheduling algorithms used in some process and network schedulers. The algorithm is designed to achieve fairness when a limited resource is shared, for example to prevent flows with large packets or processes that generate small jobs from consuming more throughput or CPU time than other flows or processes. Fair queuing is implemented in some advanced network switches and routers. History The term ''fair queuing'' was coined by John Nagle in 1985 while proposing round-robin scheduling in the gateway between a local area network and the internet to reduce network disruption from badly-behaving hosts. A byte-weighted version was proposed by Alan Demers, Srinivasan Keshav and Scott Shenker in 1989, and was based on the earlier Nagle fair queuing algorithm. The byte-weighted fair queuing algorithm aims to mimic a bit-per-bit multiplexing by computing theoretical departure date for each packet. The concept has been further developed into weighted fa ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Generalized Processor Sharing
Generalized processor sharing (GPS) is an ideal scheduling algorithm for process schedulers and network schedulers. It is related to the fair-queuing principle which groups packets into classes and shares the service capacity between them. GPS shares this capacity ''according to some fixed weights''. In process scheduling, GPS is "an idealized scheduling algorithm that achieves perfect fairness. All practical schedulers approximate GPS and use it as a reference to measure fairness." Generalized processor sharing assumes that traffic is fluid (infinitesimal packet sizes), and can be arbitrarily split. There are several service disciplines which track the performance of GPS quite closely such as weighted fair queuing (WFQ), also known as packet-by-packet generalized processor sharing (PGPS). Justification In a network such as the internet, different application types require different levels of performance. For example, email is a genuinely store and forward kind of application, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Weighted Fair Queuing
Weighted fair queueing (WFQ) is a network scheduling algorithm. WFQ is both a packet-based implementation of the generalized processor sharing (GPS) policy, and a natural extension of fair queuing (FQ). Whereas FQ shares the link's capacity in equal subparts, WFQ allows schedulers to specify, for each flow, which fraction of the capacity will be given. Weighted fair queuing is also known as packet-by-packet GPS (PGPS or P-GPS) since it approximates generalized processor sharing "to within one packet transmission time, regardless of the arrival patterns." Parametrization and fairness Like other GPS-like scheduling algorithms, the choice of the weights is left to the network administrator. There is no unique definition of what is "fair" (see for further discussion). By regulating the WFQ weights dynamically, WFQ can be utilized for controlling the quality of service Quality of service (QoS) is the description or measurement of the overall performance of a service, such ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
