Marco Chiesa Ilya Nikolaevskiy Hi Jitka, Scott discussed with Mario (Szegedy) and he said you're working on Resilient Routing Tables. I'm a visiting student at UC Berkeley working with Scott Shenker on the same topic. Ilya (cc-ed) visited UC Berkeley this year and worked on the same topic too. I am very interested in this problem and Scott said it would be a good idea to start a discussion among us. I think it would be great. This is a summary of my recent results. (In case you're interested, I'll be happy to share my notes with you) Vertex-resiliency: - Question: Given an arbitrary graph $G$, does there exist a routing scheme such that every vertex that is $k$-vertex-connected to a destination can send a packet to the destination even if $k-1$ vertex fails. Answer: for every $k$, no. - Result: Every $k$-vertex-connected chordal graph is $k-1$-vertex-resilient. - Conjecture (I still can't prove a key lemma here): Every $k$-vertex-connected graph with no induced cycle of length more than $4$ is $k-1$-vertex-resilient. Edge-resiliency: - "Circular routing" policy cannot handle $k-1$ edge-failures in a $k$-edge-connected graph. Intuitively, a circular routing policy at a vertex $v$ is an ordering of all neighbors $n_1,...,n_k$ of $v$ such that, if $v$ receives a packet from $n_1$, it sends it to $n_2$, if $v$ receives a packet from $n_2$, it sends it to $n_3$, ..., if $v$ receives a packet from $n_k$, it sends it to $n_1$. If a link to a neighbor is failed, it sends the packet to the next neighbor. The counterexample is for $k=3$. Ilya found many other interesting results. I'll try to summarize them here. Ilya please correct me in case I'm wrong. Edge resiliency: - $3$-edge-connected graphs are $2$-resilient. - there exists a $2$-edge-connected graph that is not $2$-edge-resilient. - Grids are $3$-edge-resilient. Best, Marco --------------------------------------------------------------------------- Hi Jatka, I just want to add, that we currently have several conjectures: - There always exists $k-1$-resilient routing for $k$-edge-connected graph. - $k$-edge-connected graph may not permit $k$-resilient routing. - There always exists $k-1$-resilient routing for $k$-vertex-connected graph. - $k$-vertex-connected graph may not permit $k$-resilient routing. We are trying to check them. Now we have proved edge-connected conjectures for special cases (small $k$, chordal graphs, etc). I have also generalized static routing to probabilistic routing. It always exists, but have expected number of hops before delivery larger that static routing. But that result is better to be left for the future. Now we are focused on checking conjectures. --------------------------------------------------------------------------- Hi, I was working on this topic in July. I also prove that $3$-edge-connected graphs are $2$-resilient and I belive that this prove could be generalize. I thing I could continue with this topic in my thesis. I need at least week to return to topic, find supervisor and new conjectures. Then I would like to share my notes. Jitka Novotna --------------------------------------------------------------------------- Hi Jitka, I am very interested to see your proof of 2-resilience for 3-edge-connected graphs. Generalisation of proof may be almost impossible. In my proof I used edge-independent spanning trees. If you are interested, i can send you notes. Looking forward for your reply next week. --------------------------------------------------------------------------- I just want to add, that we currently have several conjectures: - There always exists $k-1$-resilient routing for $k$-edge-connected graph. - $k$-edge-connected graph may not permit $k$-resilient routing. - There always exists $k-1$-resilient routing for $k$-vertex-connected graph. - $k$-vertex-connected graph may not permit $k$-resilient routing. We are trying to check them. Now we have proved edge-connected conjectures for special cases (small $k$, chordal graphs, etc). I have also generalized static routing to probabilistic routing. It always exists, but have expected number of hops before delivery larger that static routing. But that result is better to be left for the future. Now we are focused on checking conjectures. --------------------------------------------------------------------------- Hi, sorry, I forgot what I found. I use also three independent spanning trees. And It can noc by generalize to prove $k$-edge-connected graph is $k-1$ resilient. But I hope that it could by generalize to prove that $k$-edge-connected graph has $k$ independent spanning trees. Jitka --------------------------------------------------------------------------- Well, to my knowledge, existence of k independent trees in k-connected graphs is proved only for k<4. And for k=4 only for planar graphs. If you could generalize your proof it will be amazing result worth it's own paper or two. But it is still very hard to use more than 3 trees to organize resilient routing as we can not store information about which trees were failed before and my encounter some failed links twice which will be impossible to recover from. --------------------------------------------------------------------------- > Hi, > > I was working on this topic in July. > > I also prove that $3$-edge-connected graphs are $2$-resilient and > I belive that this prove could be generalize. > > I thing I could continue with this topic in my thesis. > I need at least week to return to topic, find supervisor and new > conjectures. > > Then I would like to share my notes. > > Jitka Novotna --------------------------------------------------------------------------- Hi Jitka, Woo, your result sounds amazing, especially if you can generalize it!!! I am very interested to see your proof idea. Take your time. Who is your advisor by the way? A doubt. Can you use your proof technique for proving 3-vertex-connectivity/2-vertex-resiliency? Looking forward to hear from you. Best, Marco --------------------------------------------------------------------------- Hi, I was working on this topic in July. I also prove that $3$-edge-connected graphs are $2$-resilient and I belive that this prove could be generalize. I thing I could continue with this topic in my thesis. I need at least week to return to topic, find supervisor and new conjectures. Then I would like to share my notes. Jitka Novotna --------------------------------------------------------------------------- Hi Jitka, I am still waiting to hear from you on your proof of 2-resilience of 3-edge-connected graph. You noted that it is possible to prove existence of $k$ independent trees in k-connected graph. If you want, i can share with you my notes. Best regards, Ilya Nikolaevskiy --------------------------------------------------------------------------- Hi,   today I presented proof of 2-resilience of 3-edge-connected graphs on our combinatorial seminar. It seem to everybody belive me this prove.   My advisor is Ondrej Pagrac http://iuuk.mff.cuni.cz/~pangrac/   Lada from our semirar thinks that 4 independent trees are not enough for 3-resilience because even cycles and 5 independent trees could be enought for 4-resilience. So I going to look on this topic.   Writing of my prove is almost complete. I use word 2-routing instead 2-resilience and there is lots bugs in my english. I going to use your terms in my next paper. I can send it to you even if it is not copmlete. Do you want?   I will be happy if you share me your notes. Do you make progress?   Jitka --------------------------------------------------------------------------- Hi, here are my notes. But there was not much progress after that. Marco proved $k-1$-resilience for any K for chordal graphs. Now we are stuck with proving resilience for C5-free graphs (graphs without induced cycles of length 5 or less) and planar graphs.