DOC PREVIEW
Berkeley COMPSCI 294 - Advanced Routing in Packet Radio Networks

This preview shows page 1-2-21-22 out of 22 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS 294-7: Advanced Routing in Packet Radio NetworksLarge Network Routing AlgorithmsSome Feasible ApproachesHierarchical AlgorithmsSlide 5Slide 6Hierarchical RoutingSlide 8Slide 9Non-Hierarchical AlgorithmsARPA Packet RadioSlide 12ARPA PacketRadioSlide 14Receiver Directed ProtocolsARPA Packet Radio: SURAN ProgramARPA Packet Radio: SURAN ProgramSlide 18SummaryUCLA WAMIS ProjectSlide 21Slide 221CS 294-7: Advanced Routing in Packet Radio NetworksProfessor Randy H. KatzCS DivisionUniversity of California, BerkeleyBerkeley, CA 94720-1776© 19962Large Network Routing Algorithms•Large Network Issues–Increasing number of node, with fixed density of nodes, yields increase in average number of hops (N0.5)»Bandwidth per user goes down by N0.5–One solution: Backbone links needed to insure that route length grows more slowly with network size–Standard protocols simply don’t work»Time for routing updates to propagate through the network grows with N0.5»This means that routing updates must be transmitted more frequently as network grows, yielding too much traffic»Event-driven routing doesn’t help: beyond some upper limit, all network bandwidth is dedicated to routing updates3Some Feasible Approaches•Hide details of distant parts of the network–Next hop decisions only depends on local region–Motivates hierarchical algorithms•Send out information about distant parts less frequently–Next hop route unlikely to change dramatically if distant part of the network undergoes topology changes–Prioritized tier connectivity information exchange algorithm: use up-to-date information as packet gets near destination•Send information only to nodes that need it–Threshold distance vector routing algorithm: if changes don’t change the quality of the route too much, don’t report the changes4Hierarchical Algorithms•Hide details via clustering of nodes•Clusters can also be aggregated into superclusters–Between superclusters: intersupercluster router–Between clusters: intercluster router•Hierarchical algorithms depend on:–How clusters and superclusters are formed–How address of destination node is determined–How routes are computed–How packets are forwarded5Hierarchical Algorithms•Supercluster/cluster hierarchy–Dynamic determination of neighbors–Election algorithms for choosing (super)cluster heads–Nodes join the nearest (super)cluster heads•Hierarchical addressing–Address servers keep track of address of specific nodes–Any node must be able to find an appropriate address server»Address server sends query to other address server to determine if the destination is in that cluster»Address servers send updates to other servers when cluster membership changes»Information about a cluster’s membership is returned along with an answer to a query and cached6Hierarchical Algorithms•Hierarchical Routing–Quasi-hierarchical»Use shortest path to the destination supercluster»Then shortest path within the destination cluster–Strict hierarchical»Routing through a sequence of intermediate superclusters»Within each supercluster, packet is routed through a sequence of intermediate clusters»Within destination supercluster, routed to destination cluster, then destination node7Hierarchical Routing•Quasi-Hierarchical–Extension of tier-routing algorithm–PROPs report shortest paths within clusters, to other clusters in supercluster, to other superclusters–Border Packet Radios»Neighboring (super)clusters are reported as one hop away—each PR’s path to a super(cluster) is shortest path to border PR»Neighboring (super)clusters reported as S hops away, where S is average distance to the (super) cluster border plus average distance from border to members of the cluster–Requires periodic routing update broadcasts Order (# nodes in cluster, # clusters in supercluster, # clusters)–Simple, but poor responsiveness to routing changes8Hierarchical Algorithms•Strict Hierarchical–Clusterheads which compute hierarchical routing tables (HRTs)»Specify next cluster to traverse to reach given dst cluster»CHs distribute this routing info to PRs in their cluster»Once destination cluster is reached, flat routing schemes are used to deliver packet to destination–Event-driven routing for intercluster: intercluster connectivity likely to change slowly, but can react quickly when topology changes do occur–Reduces amount of information necessary for a node to make routing decisions–Weakness is the clusterhead: hot standby mechanisms needed for robust routing9Hierarchical Algorithms•Landmark Routing–Variation on quasi-hierarchical routing–Distance vector used to compute routes to other nodes BUT destinations dropped from tier table if too far away»Top of hierarchy: mentioned in every route update—“Global landmark”»Leaves of hierarchy: only included in updates to nearby nodes»Address of node is sequence of landmarks: global landmark to destination node’s parent»Routing done by forwarding packet to lowest level landmark visible to the forwarding node–Similar advantages and disadvantages to the quasi-hierarchical routing algorithm10Non-Hierarchical Algorithms•Prioritized Tier Connectivity Information Exchange–Routes characterized by priority based on rate of change–Single distance vector routing update per period–Rapidly changing routes transmitted frequently–Infrequently changing routes transmitted infrequently•Threshold Distance Vector Routing Algorithm–Reduces the distance over which routing updates are propagated–dj + cj  d  dj +  cj»d is distance to destination»j is next node on path»c is cost of using link to j»if  is increased, fewer update messages are transmitted and path lengths increase slightly11ARPA Packet Radio•Strict Hierarchical Routing–Used in ARPA PR program because quasi-hierarchical algorithms were shown to be unstable in highly dynamic networks–Intracluster algorithm: the existing tier algorithm is used–Intercluster algorithm: event-driven link-state algorithm»Participate in two clusters at a time: current cluster and previous or next cluster»Each PROP includes routes to all PRs in all clusters it has joined–Cluster partitions»PR cannot route to its cluster’s clusterhead»PR must leave the cluster as soon as possible12ARPA Packet RadioA|A|AA|A|BA|B|BB|B|BPrevious Cluster = ACurrent Cluster = ANext Cluster = ATypicalStatePR moves towardsCluster B and willjoin itJoins B


View Full Document

Berkeley COMPSCI 294 - Advanced Routing in Packet Radio Networks

Documents in this Course
"Woo" MAC

"Woo" MAC

11 pages

Pangaea

Pangaea

14 pages

Load more
Download Advanced Routing in Packet Radio Networks
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Advanced Routing in Packet Radio Networks and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Advanced Routing in Packet Radio Networks 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?