Node Weighted Scheduling

Computer Science – Networking and Internet Architecture

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

To appear in Sigmetrics 2009

Scientific paper

This paper proposes a new class of online policies for scheduling in input-buffered crossbar switches. Our policies are throughput optimal for a large class of arrival processes which satisfy strong-law of large numbers. Given an initial configuration and no further arrivals, our policies drain all packets in the system in the minimal amount of time (providing an online alternative to the batch approach based on Birkhoff-VonNeumann decompositions). We show that it is possible for policies in our class to be throughput optimal even if they are not constrained to be maximal in every time slot. Most algorithms for switch scheduling take an edge based approach; in contrast, we focus on scheduling (a large enough set of) the most congested ports. This alternate approach allows for lower-complexity algorithms, and also requires a non-standard technique to prove throughput-optimality. One algorithm in our class, Maximum Vertex-weighted Matching (MVM) has worst-case complexity similar to Max-size Matching, and in simulations shows slightly better delay performance than Max-(edge)weighted-Matching (MWM).

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Node Weighted Scheduling does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Node Weighted Scheduling, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Node Weighted Scheduling will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-311607

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.