White Papers

Reducing Maximum Stretch in Compact Routing

Overview It is important in communication networks to use routes that are as short as possible (i.e have low stretch) while keeping routing tables small. Recent advances in compact routing show that a stretch of 3 can be achieved while maintaining a sub-linear space at each node. It is also known that no routing scheme can achieve stretch less than 3 with sub-linear space for arbitrary networks. In contrast, simulations on real-life networks have indicated that stretch less than 3 can indeed be obtained using sub-linear sized routing tables. This paper further investigate the space-stretch tradeoffs for compact routing by analyzing a specific class of graphs and by presenting an efficient algorithm that (approximately) finds the optimum space-stretch tradeoff for any given network.

By downloading you agree to our Terms and Conditions. These include information regarding use of your personal data.

Publisher: Stanford University
File Format: PDF
Date Published: Jul 11, 2008
Format: White Papers
Topics: Diagnostics and Analysis, Switching

Similiar White Papers

Next-Generation Switch/Router Diagnostics and Debugging

The goal for a next-generation diagnostics and debugging system for switch/routers is to improve system uptime and avail

Publisher: Force10 Networks | Tags: routers

How Cisco IT Uses Analysis Module to Gather Information on Host, Network, and Application Traffic

The Cisco team needed a solution that could provide more than packet capture. They needed to look at the application lay

Publisher: Cisco Systems | Tags: ip, network, qos, real-time, voip, wan

Reviewer's Guide: ProCurve 5400zl, 3500yl and 6200yl Switches

This Reviewer's Guide from ProCurve Networking by HP is a valuable resource for those researching or evaluating high-per

Publisher: Hewlett-Packard (HP) | Tags: ethernet

Open Shortest Path First (OSPF) Conformance and Performance Testing

The Open Shortest Path First (OSPF) routing protocol has been gaining support as the most popular Interior Gateway Proto

Publisher: Ixia | Tags: ip, network

Network Monitoring and Analysis Techniques Using Taps and SPAN Switches

Networks have evolved into complex structures supporting critical business processes and communications. As this complex

Publisher: Fluke Networks | Tags: management, network, network management

Stanford University White Papers

Modeling Signal Attenuation in IEEE 802.11 Wireless LANs - Vol. 1

Featured white papers

The Value of Location Intelligence in the Communications Industry

Pitney Bowes

Public Services are under pressure, the challenge is to do more with less. How do you improve citizen satisfaction, increase cost efficiencies and improve service delivery? The power of location intelligence is helping many local authorities...

Download now »
Best Practices for Translating Customer Satisfaction into Revenue

Citrix Online

Today's support organisations are focused on two top-level metrics: financial results and customer satisfaction. For most, it's easy to track financial performance, but customer satisfaction is akin to speaking a foreign language...

Download now »
HP print solutions and 3M

Hewlett-Packard (HP)

The objective for 3M was to optimize office printing infrastructure at 3M locations worldwide, reduce total cost and environmental footprint. Some of the business benefits acheived by switching to HP print solutions...

Download now »