Abstract: Greedy routing is a message-passing strategy used in network communication, particularly in scenarios involving geometric or spatial networks. It is a simple and intuitive method where, at each step of the routing process, a node chooses to send a given packet to the neighbor that is closest to the destination based on a certain metric. Greedy routing is often used in networks where nodes have geographic locations, such as sensor networks, wireless ad-hoc networks, or routing in the context of geographic information systems (GIS) such as road networks. Greedy routing traces its origins to famous experiments by the social-psychologist, Stanley Milgram, in the 1960s, exploring the "small-world phenomenon" that people are connected through a short chain of acquaintances that can be used to route messages. This talk revisits this classic work from the perspective of asking what additional links need to be added to a network, such as the U.S. road network or a sensor grid network, to support fast greedy routing. To this end, we introduce the Neighborhood Preferential Attachment model, which combines elements from previous social-network models with simple geographic considerations, so that long-range links are chosen according to both node degrees and network distances. We empirically and theoretically evaluate this model using spatial networks, showing, for instance, that our model can empirically explain Milgram's findings that people living in the U.S. have at most 6 degrees of separation and, more importantly, their social network supports efficient greedy routing.
Bio: Michael Goodrich received his B.A. in Mathematics and Computer Science from Calvin University in 1983 and his PhD in Computer Science from Purdue University in 1987. He is a Distinguished Professor at the University of California, Irvine, where he has been a faculty member in the Department of Computer Science since 2001. Dr. Goodrich's research is directed at the design of high performance algorithms and data structures with applications to information assurance and security, the Internet, machine learning, and geometric computing. He has pioneered and led research on efficient solutions to a number of fundamental problems, including sorting, convex hull construction, nearest-neighbor searching, linear programming, privacy-preserving data access, network traceback, and data authentication. With over 350 publications, including several widely-adopted books, his work includes contributions to efficient and secure distributed data structures, information privacy, social networks, and cloud security. He is an ACM Distinguished Scientist, a Fellow of the American Association for the Advancement of Science (AAAS), a Fulbright Scholar (with senior specialist service in Denmark), a Fellow of the IEEE, and a Fellow of the ACM. He is a recipient of the IEEE Computer Society Technical Achievement Award, the Brown Univ. Award for Technological Innovation, and the Pond Award for Excellence in Undergraduate Teaching.
Abstract: Greedy routing is a message-passing strategy used in network communication, particularly in scenarios involving geometric or spatial networks. It is a simple and intuitive method where, at each step of the routing process, a node chooses to send a given packet to the neighbor that is closest to the destination based on a certain metric. Greedy routing is often used in networks where nodes have geographic locations, such as sensor networks, wireless ad-hoc networks, or routing in the context of geographic information systems (GIS) such as road networks. Greedy routing traces its origins to famous experiments by the social-psychologist, Stanley Milgram, in the 1960s, exploring the "small-world phenomenon" that people are connected through a short chain of acquaintances that can be used to route messages. This talk revisits this classic work from the perspective of asking what additional links need to be added to a network, such as the U.S. road network or a sensor grid network, to support fast greedy routing. To this end, we introduce the Neighborhood Preferential Attachment model, which combines elements from previous social-network models with simple geographic considerations, so that long-range links are chosen according to both node degrees and network distances. We empirically and theoretically evaluate this model using spatial networks, showing, for instance, that our model can empirically explain Milgram's findings that people living in the U.S. have at most 6 degrees of separation and, more importantly, their social network supports efficient greedy routing.
Bio: Michael Goodrich received his B.A. in Mathematics and Computer Science from Calvin University in 1983 and his PhD in Computer Science from Purdue University in 1987. He is a Distinguished Professor at the University of California, Irvine, where he has been a faculty member in the Department of Computer Science since 2001. Dr. Goodrich's research is directed at the design of high performance algorithms and data structures with applications to information assurance and security, the Internet, machine learning, and geometric computing. He has pioneered and led research on efficient solutions to a number of fundamental problems, including sorting, convex hull construction, nearest-neighbor searching, linear programming, privacy-preserving data access, network traceback, and data authentication. With over 350 publications, including several widely-adopted books, his work includes contributions to efficient and secure distributed data structures, information privacy, social networks, and cloud security. He is an ACM Distinguished Scientist, a Fellow of the American Association for the Advancement of Science (AAAS), a Fulbright Scholar (with senior specialist service in Denmark), a Fellow of the IEEE, and a Fellow of the ACM. He is a recipient of the IEEE Computer Society Technical Achievement Award, the Brown Univ. Award for Technological Innovation, and the Pond Award for Excellence in Undergraduate Teaching.