Scheduling1

    • Outline
    • Scheduling
    • Components:

    Decides Server order

    manage queue

    • Why do we need one?
    • What can scheduling disciplines do?
    • Requirements of a scheduling discipline
    • Ease of implementation
    • Fairness

    Fairness is global, scheduling(congestion avoidance) is local.

    • Notion of Fairness
    • Fundamental choices

    Work-conserving and non-work-conserving

    Degree of aggregation

    • Scheduling disciplines

    FIFO & other disciplines(SPT, SRPT), the performance among them

    (SRPT process the remaining time, which means if I’m processing a package which still needs 5 min, then comes a package which only need 1 min, then I go to process the new package)

     

    • The Conservation Law

    scheduling is independent of the packet service time

    [latex]\sum ρ_iq_i=constant[/latex]

    [latex]ρ_i[/latex] mean utilization of connection i and [latex]q_i[/latex] mean waiting time of connection i

    The average delay with FIFO is a tight lower bound for
    work conserving and service time independent scheduling
    disciplines

    • Fairness

    Jain’s index use equal share as the
    objective:

    [latex]f=\frac{(\sum_{i=1}^{N}x_i)^2}{(n\sum_{i=1}^{N}x_i^2)}[/latex]

    • Max-Min Fairness
    • General Process Sharing (GPS)

    Conceptually, GPS serves packets as if they are
    in separate logical queues, visiting each nonempty
    queues in turn.

    Generalized processor sharing assumes that traffic is fluid (infinitesimal packet sizes), and can be arbitrarily split.

    How to emulate GPS as fair as possible, also efficient

    • (Weighted) round robin

    Different weights, fixed packet size

    Different weights, variable size packets:normalize weights by mean packet size

    Problems:

    1. With variable size packets and different weights,
      need to know mean packet size in advance
    2. Can be unfair for long periods of time
    Categories: 未分类

    Registration Notes

    This note is for CS5240

    Last time we discussed Rigid & Nonrigid and their methods:

    [su_table]

    Rigid Nonrigid
    similarity transformation affine transformation
    ICP nonrigid ICP

    [/su_table]

    Methods below are approximation. Now we discuss interpolation.

    Thin Plate Spline

    How to get TPS?

    [su_custom_gallery source=”media: 243″ limit=”19″ target=”blank” width=”800″ height=”480″]

    Minimizing bending energy!TPS maps [latex]p_i[/latex] to [latex]q_i[/latex] exactly.

    Consider jth component [latex]v_{ij}[/latex] of [latex]q_i[/latex], TPS maps [latex]p_i[/latex] to [latex]v_{ij}[/latex] by [latex]f(p_i)=v_{ij}[/latex] which minimize bending energy denoted as [latex]E_d(f)[/latex].

    Bending energy function takes two parameters the first is d(the dimension of the point), the second is m, which denotes order-m derivatives.

    Finally the function f that minimize the Bending energy takes the form

    [latex]f(x’) = a^Tx’+\sum_{i=1}^{n} w_iU(||x-p_i||)[/latex]

    a are affine parameters. w are weights. U(r) is increasing function of distance r.

     

     

    Categories: 未分类