Thread by @fgrosshans

Now at #IWQNS, Prithwish Basu from U. Massachusetts on Routing and Scheduling in cClassiacal Networks #LTQI

Prithwish Bashu: Modern networks are not like internet in the 1970s. They’re no longer nice graphs, but now some king of hypergraphs with a mishmash of technologies.
#IWQNS #LTQI

Prithwish Basu: look at multi-hop routing in ad-hoc wirelss networks. Scheduling can be used to limit interference. In these networks, routing and scheduling cannot really be looking independently. #LTQI #IWQNS

Prithwish Basu: A scheduling policy is equivalent to 2-hop graph coloring (nodes need to be 3-hops away to get same color). This an NP hard problem, but with efficient approximations.
#LTQI #IWQNS

Prithwish Basu: Optimizing one metric (delay, reliability) is polynomial :-) But as soon as you want to optimize two metrics simultaneously, you’re immediately in an NP-hard problem.
#IWQNS #LTQI

Prithwish Basu: bookkeeping needed to compute routes, especially with dynamic topologies of mobile networks.
For slow dynamics and low traffic load, on-demand routing is better. For fast dynmanics and high traffic load, proactive updates of network state is better #IWQNS #LTQI

Prithwish Basu: Routing is global problem. One solution, is through a tree embedded in hyperbolic geometry, where a greedy algorithm is optimal. But updating the tree can be complex.
#IWQNS #LTQI

Prithwish Basu: Routing flow over multiple path can be complicated. For a single commodity, min cut (φ) = max flow (f). But for 2 commodities or more, we can have different values f < φ, and it his NP-complete to compute.
#LTQI #IWQNS

Prithwish Basu: What if each link failed probabilistically ? One can reformulate the generalized max flow in directed graph, computing its expected value in poly time through linear programming.
#LTQI #IWQS

Prithwish Basu: Using backpressure mechanisms for routing and scheduling, we get maximum stable throughput.Routing is based on maximal differential queue backlog. Then Scheduling maximizes the sum of queue backlogs (NP-hard, but ∃ heuristics)
#IWQNS #LTQI

Prithwish Basu now looks at multicast routing through network coding. In theory it increases capacity, but in practice, it is not used: needs Galois field computation/packet, and compatibility with other layers problematic
#LQIE #IWQNS

@threadreaderapp Please kindly unroll...