A Personal Viewof ToNC.ppt

1、A Personal View of ToNC,Christos H. Papadimitriou UC Berkeley“christos”,ToNC, March 16 2006,2,Why I work in ToNC,What else is there? Ideology meets competence Opportunity to do Game Theory Theory & experiment Cool playmates,ToNC, March 16 2006,3,Outline,“CToNC” Algorithms, games and networks Vignett

2、e 1: Greedy routing Vignette 2: The crowded center problem Vignette 3: The economics of privacy,ToNC, March 16 2006,4,“CToNC”,Proving the last theorem Think of it as a call to arms Read the classics With any luck, there will be a couple of them,ToNC, March 16 2006,5,NetComp and Game Theory,Three pro

3、ngs: Computational mechanism design Price of anarchy Algorithms for equilibria This is going well (But may be at a juncture where infusion of new ideas is needed),ToNC, March 16 2006,6,Routing in sensornets,IP envy Use geography? Greedy Routing: “Give the packet to your neighbor who is closest to th

4、e destination”,ToNC, March 16 2006,7,Greed can hurt you (30% of the time),packet from here,to there,“lake”,gets stuck here,remedy: face routing,ToNC, March 16 2006,8,Idea: fake coordinates,greedy embedding: greedy is distance-decreasing,ToNC, March 16 2006,9,How do you find the fake coordinates?,By

5、rubber bands! PRRSS 03 Is there always a “greedy embedding?” Conjecture PR05: Every planar, 3-connected graph has a greedy embedding in the plane (True for 3D) Theorem K06: Every graph has a greedy embedding in the hyperbolic plane,ToNC, March 16 2006,10,ToNC, March 16 2006,11,The burden of being ce

6、ntral KPPRS 06,Q: How do you relieve the center?,ToNC, March 16 2006,12,The burden of being central KPPRS 06,Q: How do you relieve the center?A: By curveball routingQ: Optimal?,ToNC, March 16 2006,13,Optimum by LP,max c x Ax = 1 Bx t x 0,limit on congestion, one constraint per “ring”,path lengths,on

7、e variable per path, a continuum of variables,dual: min + t AT + BT -c 0,“speed of light” as a function of r,ToNC, March 16 2006,14,Geometric optics!,Primal-dual: restricted primal is path of light under Snells law When lights speed is (r)Or simple iterative algorithm: “if congestion is too high at

8、r, decrease speed of light (r)” Still running,ToNC, March 16 2006,15,The economics of privacy KPR01,Definition is elusive! Personal data: IP bearing negative royalty Opportunistic possession exploited e.g., need for printer vs printer budget Challenge: Calculate fair royalty Methodology: Cooperative game theory,