Reference http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=00869208 http://www.cs.berkeley.edu/~kfall/papers/rfn.pdf
| What is LANDMARK Routing |
Landmark Routing has the following features:
- operates efficiently and automatically in networks of large size
- responds to changing network conditions such as topology changes
- provides full name-based addressing
- provides automatic address assignment
- accommodates administrative boundaries, providing control of routing paths, protection, and autonomy
| Landmark Router |
- A Landmark is a router whose neighbor routers within a certain number of hops contain routing entries for that router.
- LMi refers to a Landmark of hierarchy level i, i=O being the lowest level, and i=H being the highest level.
- LMi[id] refers to a specific LMi, with label id, called the Landmark ID
- ri[id] is a radius of a corresponding LMi[id].
- In the Landmark Hierarchy, every router in a network is a Landmark LM0[id] of some small radius r0[id].
| ROUTING |
(1). Routing Table Each router keeps a table of the next hop on the shortest path to each Landmark for which it has routing entries.
(2). Addressing The address of a router is a series of Landmark IDs of the Landmarks at each hierarchical level which the router is near.
Each Landmark in the address must be within the radius of the Landmark with next lower Landmark ID in the address. E.g. let’s consider a Landmark Address LM2[c].LM1[b].LM0[a]. LM2[c] is called a parent of LM1[b], and LM1[b] is called a child of LM2[c].
(3). Routing Finding a path from the router Source to the router LM0[a].
[ Dynamic Algorithms in Landmark Routing ]
(1). Hierarchy management algorithm
Needed for assigning landmarks and determining their corresponding radii
The hierarchy is built from the bottom up. Each Landmark has 3 or 4 children in steady state. 1 is the minimum number of children, while 7 is the maximum number of children.
(2).Routing algorithm Needed for discovering Landmarks and for establishing paths to Landmarks.
Must be of the distance-vector type Every router periodically informs its neighbors of it’s distance to one or several destinations. When the neighbor receives such information, it adds its own distance to its neighbors to the distance it had received and decrements the Landmark radius. The distance to the destination is considered to be smallest of the received distances. And the next hop to the destination is the one over which this shortest distance was received.
(3). Algorithm for binding permanent names or IDs to changing addresses Assured Destination Binding (ADB)
Conclusion
- The performance of the Landmark Hierarchy depends on the r/d ratio, where
- ri is the radius of the Landmark
- di is the distance from a router to the nearest level i Landmark
- The Landmark Hierarchy doesn’t perform well for networks with very small diameters compared to the number of routers.
Further
01.Distributed Compact Routing
02.LANMAR
