| Systems and methods for weighted best effort scheduling -> Monitor Keywords |
|
|
  Systems and methods for weighted best effort schedulingRelated Patent Categories: Multiplex Communications, Pathfinding Or Routing, Switching A Message Which Includes An Address Header, Message Transmitted Using Fixed Length Packets (e.g., Atm Cells), Assigning Period Of Time For Information To Be Transmitted (e.g., Scheduling)The Patent Description & Claims data below is from USPTO Patent Application 20060233177. Brief Patent Description - Full Patent Description - Patent Application Claims
FIELD [0001] The present invention is in the field of digital processing. More particularly, the invention is in the field of allocating bandwidth in a network processor. BACKGROUND [0002] Many different types of computing systems have attained widespread use around the world. These computing systems include personal computers, servers, mainframes and a wide variety of stand-alone and embedded computing devices. Sprawling client-server systems exist, with applications and information spread across many PC networks, mainframes and minicomputers. In a distributed system connected by networks, a user may access many application programs, databases, network systems, operating systems and mainframe applications. Computers provide individuals and businesses with a host of software applications including word processing, spreadsheet, accounting, e-mail, voice over Internet protocol telecommunications, and facsimile. [0003] In today's networked world, bandwidth is a critical resource. Very high network traffic, driven by the Internet and other emerging applications, is straining the capacity of network infrastructures. To keep pace, organizations are looking for better ways to support and manage traffic growth and the convergence of voice with data. Today's dramatic increase in network traffic can be attributed to the popularity of the Internet, a growing need for remote access to information, and emerging applications. The Internet alone, with its explosive growth in e-commerce, has placed a sometimes insupportable load on network backbones. The growing demands of remote access applications, including e-mail, database access, and file transfer, are further straining networks. [0004] Eliminating network bottlenecks continues to be a top priority for service providers. Routers are often the source of these bottlenecks. However, network congestion in general is often misdiagnosed as a bandwidth problem and is addressed by seeking higher-bandwidth solutions. Today, manufacturers are recognizing this difficulty. They are turning to network processor technologies to manage bandwidth resources more efficiently and to provide the advanced data services, at wire speed, that are commonly found in routers and network application servers. These services include load balancing, QoS, gateways, fire walls, security, and web caching. [0005] A Network Processor (NP) may be defined as a programmable communications integrated circuit capable of performing one or more of the following functions: [0006] Packet classification--identifying a packet based on known characteristics, such as address or protocol [0007] Packet modification--modifying the packet to comply with IP, ATM, or other protocols (for example, updating the time-to-live field in the header for IP) [0008] Queue/policy management--reflects the design strategy for packet queuing, de-queuing, and scheduling of packets for specific applications [0009] Packet forwarding--transmission and receipt of data over the switch fabric and forwarding or routing the packet to the appropriate address [0010] Although this definition accurately describes the basic features of early NPs, the full potential capabilities and benefits of NPs are yet to be realized. Network processors can increase bandwidth and solve latency problems in a broad range of applications by allowing networking tasks previously handled in software to be executed in hardware. In addition, NPs can provide speed improvements through certain architectures, such as parallel distributed processing and pipeline processing designs. These capabilities can enable efficient search engines, increase throughput, and provide rapid execution of complex tasks. [0011] Network processors are expected to become the fundamental network building block for networks in the same fashion that CPUs are for PCs. Typical capabilities offered by an NP are real-time processing, security, store and forward, switch fabric, and IP packet handling and learning capabilities. The processor-model NP incorporates multiple general purpose processors and specialized logic. Suppliers are turning to this design to provide scalable, flexible solutions that can accommodate change in a timely and cost-effective fashion. A processor-model NP allows distributed processing at lower levels of integration, providing higher throughput, flexibility and control. Programmability can enable easy migration to new protocols and technologies, without requiring new ASIC designs. [0012] A network processor comprises circuitry to schedule transmission of packets. Packets are scheduled for transmission according to the bandwidth allocated to each flow of packets. Multiple flows of packets may be destined for the same port or channel. The channel or port is band limited. For example, a 10 Ghz Sonet link may time-division multiplex 192 channels at about 51.84 Mega-bits per second (Mb/s). Each channel can be further multiplexed into 32 T1/E1 sub-channels. Thus, the link provides 192.times.32>6000 channels. Each flow destined for a channel must share it with other flows destined for the same channel. A best-effort scheduler schedules data packets for transmission according to a priority assigned to the flow queue to which each packet belongs. Since there are multiple flows and many channels in a typical system, one desires to minimize the hardware resources required to schedule packets for transmission. SUMMARY [0013] The problems identified above are in large part addressed by systems and methods disclosed herein for implementing a scheduler in a network processor. Embodiments comprise a memory to store schedule control blocks in a first, second, and third LIFO buffer. Each LIFO buffer is adapted to store a linked-list of schedule control blocks. Each schedule control block is associated with a packet of data and comprises a weight and a counter. First, second, and third calendar entries are associated with the first, second, and third LIFO buffers, respectively. Each calendar entry is adapted to store an address for a first-out schedule control block in the linked-list of schedule control blocks stored in the LIFO buffer associated with the calendar entry. Embodiments further comprise control circuitry to increment a counter of a first-out schedule control block accessed from one of the first and second LIFO buffers. The control circuitry moves the first-out schedule control block from the one LIFO buffer to the other of the first and second LIFO buffers if the incremented counter is less than the weight. The control circuitry moves the first-out schedule control block from the one LIFO buffer to the third LIFO buffer if the incremented counter equals the weight. [0014] In one embodiment, a network processor for processing packets of data, comprises a data flow unit to receive packets of data, and for each packet, to determine a flow queue to which the packet belongs, and to transmit processed packets. The network processor also comprises an embedded processors complex comprising a plurality of processors to process packet data. A memory is provided to store schedule control blocks in a first, second, and third LIFO buffer, each LIFO buffer adapted to store a linked-list of schedule control blocks, each schedule control block comprising a weight and a counter. First, second, and third calendar entries are associated with the first, second, and third LIFO buffers, respectively. Each calendar entry is adapted to store an address for a first-out schedule control block in the linked-list of schedule control blocks stored in the LIFO buffer associated with the calendar entry. Control circuitry increments a counter of a first-out schedule control block from one of the first or second LIFO buffers. The scheduler moves the first-out schedule control block from the one LIFO buffer to the other of the first and second LIFO buffers if the incremented counter is less than the weight, and moves the first-out schedule control block from the one LIFO buffer to the third LIFO buffer if the incremented counter equals the weight. [0015] Another embodiment is a method for scheduling packets of data in a network processor. The method comprises storing schedule control blocks in linked lists, each schedule control block associated with a packet of data and comprising a weight associated with a scheduling priority. Each schedule control block stored in the first linked list is sequentially accessed. Each schedule control block stored in the second linked list is also sequentially accessed. Each time a schedule control block is accessed, a scheduling event is generated to schedule the packet associated with the accessed schedule control block. The method further comprises incrementing a counter in a schedule control block each time a schedule control block is accessed from the first or second linked lists. Each time a schedule control block is accessed, the counter of the accessed schedule control block is compared to the weight assigned to the schedule control block. The schedule control block is transferred from one of the first and second linked lists to the other of the first and second linked list, if the compared counter value does not equal the weight assigned to the schedule control block. The schedule control block is transferred from one of the first and second linked lists to a third linked list and the counter of the schedule control block is reset, if the compared counter value equals the weight assigned to the schedule control block. BRIEF DESCRIPTION OF THE DRAWINGS [0016] Other objects and advantages of the invention will become apparent upon reading the following detailed description and upon reference to the accompanying drawings in which, like references may indicate similar elements: [0017] FIG. 1 depicts a plurality of network processors serving a network; each network processor comprising a data flow unit, and embedded processors complex, a scheduler, and control and data stores. [0018] FIG. 1A depicts an embodiment of an embedded processor complex, with a plurality of processors operating in parallel to process packet data. [0019] FIG. 2 depicts an embodiment of a data flow unit comprising a receiver controller, a transmitter controller, and an EPC interface controller. [0020] FIG. 3 depicts an embodiment of a scheduler with a three-entry calendar. [0021] FIG. 4 depicts an example of scheduling with a three-entry calendar. [0022] FIG. 5 depicts a flow chart of an embodiment for scheduling with a three-entry calendar. DETAILED DESCRIPTION OF EMBODIMENTS [0023] The following is a detailed description of example embodiments of the invention depicted in the accompanying drawings. The example embodiments are in such detail as to clearly communicate the invention. However, the amount of detail offered is not intended to limit the anticipated variations of embodiments; but, on the contrary, the intention is to cover all modifications, equivalents, and alternatives falling within the spirit and scope of the present invention as defined by the appended claims. The detailed descriptions below are designed to make such embodiments obvious to a person of ordinary skill in the art. Continue reading... Full patent description for Systems and methods for weighted best effort scheduling Brief Patent Description - Full Patent Description - Patent Application Claims Click on the above for other options relating to this Systems and methods for weighted best effort scheduling patent application. ###  How KEYWORD MONITOR works... a FREE service from FreshPatents1. Sign up (takes 30 seconds). 2. Fill in the keywords to be monitored. 3. Each week you receive an email with patent applications related to your keywords. Start now! - Receive info on patent apps like Systems and methods for weighted best effort scheduling or other areas of interest. ### Previous Patent Application: Method and system for power efficient transmission of scalable video over wireless networks Next Patent Application: Method and system using arp cache data to enhance accuracy of asset inventories Industry Class: Multiplex communications ### FreshPatents.com Support Thank you for viewing the Systems and methods for weighted best effort scheduling patent info. IP-related news and info Results in 0.41057 seconds Other interesting Feshpatents.com categories: Novartis , Pfizer , Philips , Polaroid , Procter & Gamble , |
||
