Cell as SKU in intra-vc scheduler

[abuccts]

New cell as SKU feature in intra-vc scheduler, work items:

• [x] new interface for pod group and scheduling result placement
• [x] pod request parsing and conversion
• [x] affinity group / pod group adjustments before intra-vc scheduler
• [x] new scheduling algorithm in intra-vc scheduler
• [x] scheduling placements adjustments
• [x] update original test cases (leaf cell) #37
• [x] spec, request examples and document, design document
• [x] add new test cases (within feature) #38
• [x] end-to-end tests and debug

[codecov-commenter]

Codecov Report

Merging #34 (5c1e5c8) into master (66f26ac) will decrease coverage by 7.78%. The diff coverage is n/a.

@@            Coverage Diff             @@
##           master      #34      +/-   ##
==========================================
- Coverage   88.46%   80.68%   -7.79%     
==========================================
  Files           8       10       +2     
  Lines        1890     2205     +315     
==========================================
+ Hits         1672     1779     +107     
- Misses        166      334     +168     
- Partials       52       92      +40     

Flag	Coverage Δ
unittests	80.68% <ø> (-7.79%)	:arrow_down:

Flags with carried forward coverage won't be shown. Click here to find out more.

Impacted Files	Coverage Δ
...ft/hivedscheduler/pkg/algorithm/cell_allocation.go	59.90% <0.00%> (-32.37%)	:arrow_down:
...om/microsoft/hivedscheduler/pkg/algorithm/utils.go	76.09% <0.00%> (-9.30%)	:arrow_down:
...ft/hivedscheduler/pkg/algorithm/hived_algorithm.go	76.59% <0.00%> (-8.65%)	:arrow_down:
...hivedscheduler/pkg/algorithm/intra_vc_scheduler.go	100.00% <0.00%> (ø)
...cheduler/pkg/algorithm/topology_aware_scheduler.go
...microsoft/hivedscheduler/pkg/algorithm/types_v2.go	89.82% <0.00%> (ø)
...dscheduler/pkg/algorithm/hived_algorithm_tester.go	66.42% <0.00%> (ø)
...uler/pkg/algorithm/topology_guarantee_scheduler.go	92.88% <0.00%> (ø)
...m/microsoft/hivedscheduler/pkg/algorithm/config.go	96.46% <0.00%> (+0.11%)	:arrow_up:
...om/microsoft/hivedscheduler/pkg/algorithm/types.go	90.62% <0.00%> (+5.58%)	:arrow_up:

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update 66f26ac...5c1e5c8. Read the comment docs.

[yqwang-ms]

Only backtrace to parent pod group may not enough to find the whole pod root group placement if it exist in theory. Consider the following example: Only backtrace to parent, result in no solution, but in theory, a solution exist.

We can add more pod group sorting criterias, such as if it has withinOneCell requirement, but still cannot prove only backtrace to parent is enough.

So given pod group trees are generally small trees with few nodes, backtrace to previous bound pod group (i.e. parent or left sibling node) should not too time consuming, which is enough to find the whole pod root group placement if it exist in theory.

---

In reply to: 918971150

[yqwang-ms]

Add demo here, such as pods withinOneCell and single pod's non-leaf cell type #WontFix

---

Refers to: example/feature/README.md:2 in c5e1bf1. [](commit_id = c5e1bf14e62631e2d9e2899694b72e154a8829b1, deletion_comment = False)