CS 294-7: Routing in Packet Radio NetworksPacket Radio Network Schemes (ARPA PR Program)Slide 3Slide 4Packet Radio Network IssuesSlide 6DARPA Packet Radio NetworkRouting in Small to Medium Sized NetworksSlide 9Alternative Routing MetricsLink Connectivity and Route CalculationSlide 12Slide 13Forwarding ProtocolsForwarding ProtocolSlide 16Slide 17Slide 18Slide 19Slide 20Transmission ProtocolsSlide 22Slide 23Slide 24Loop Formation and How to Avoid ItExtensionsSlide 27Slide 28Event Driven Routing ExampleInteractions and Complexities1CS 294-7: Routing in Packet Radio NetworksProfessor Randy H. KatzCS DivisionUniversity of California, BerkeleyBerkeley, CA 94720-1776© 19962Packet Radio Network Schemes(ARPA PR Program)•Passive Acknowledgments–Half duplex operation: transmit packet, go into receive mode, receive ack, receive next packet, go into transmit mode, repeat–Original sender hears forwarding transmission from next hop node in the route:–Power control: transmit with enough power to be heard at D as well as FD E FD transmits to E E transmits to FD hears E to F transmissionas implicit ACK3Packet Radio Network Schemes(ARPA PR Program)•Alternative Routing on Retransmission–Packet contains header for next node on route–After multiple tries, if no ack, header changed to indicate that ANY closer node to ultimate destination may forward the packetB CE FE attempts multipletransmissions to Fbut gets no ACKFinal attempt allowsB to forward packetif it can hear transmissionfrom ERoute fromE to C4Packet Radio Network Schemes(ARPA PR Program)•Filtering Based on Overheard Traffic–Alternative routing scheme can cause undesirable packet flooding (i.e., multiple nodes forwarding on the same packet)–If packet is queued at a node X, and X hears the same packet sent from a different node, it assumes an implicit ack and removes the packet from its send queueB CE FJGE tries to transmitto B but failsF and J heartransmissionand will forwardF sends firstJ removes packetfrom its queueRoute fromE to C5Packet Radio Network Issues•Channel Access and Hidden Terminals•Throughput–Assume uniform traffic, slotted Aloha access method, K average neighbors, and H average # of hops–For single hop, implies .36/K * available ch b/w–For multihop, implies .36/(H * K)–Must also add ack and retransmission overheads–For a given radio on a packet path, must receive packet, retransmit packet, and receive ack: max 1/3 of available b/w–Clearly works best when traffic is bursty!•Connectivity–Poor channels implies link layer ack schemes–Exchange of connectivity packets: Link quality = ƒ(packets received, total packets sent)–Must be able to deal with network partitions6Packet Radio Network Issues•Broadcast Nature of Radio Channels–Nodes can overhear the forwarding of packets by other nodes–This capability can be exploited to»Send network-control traffic to all neighbors»Support algorithms for broadcasting user traffic»Circumvent link failure by finding an alternative node to route the packet7DARPA Packet Radio Network•Low cost packet radios in 1983 technology–DS spread spectrum–Multiple transmission rates (100, 400 kbps)—trade error coding for b/w when the link is good–Adaptable FEC coding, can be changed on a packet by packet basis–Up to 10 km range–Broadcast and receiver-directed packet transmission»Former uses a code sequence known to all radios»Latter uses a unique code for the target receiver;Other receivers won’t be able to extract bit sync, and will be free to receive another packet8Routing in Small to Medium Sized Networks•Optimal Routing Schemes:–Need estimates of network flows, fixed topology, residual capacity of links or incremental delay of links–Assumes independence from traffic on other links/paths•Difficult to use because:–Info about network flows NOT generally available in datagram networks–Underlying network topology can change rapidly–Delay/capacity parameters change more rapidly than topology, yielding increased overhead to keep information up to date–Information for routing purposes likely to be out of date by the time it is fully disseminated throughout the network–Delay/capacity of a link is a function of traffic on other links9Routing in Small to Medium Sized NetworksA B CD E FL M NH I JGKTransmissionsalong the redand black routeswill mutuallyinterfereAlternative routes withmore hops but less interference10Alternative Routing Metrics•Least Interference Routing (LIR)–Determine routing cost based on the number of radios that can overhear transmissions on the link–Only needs nearest neighbor information•Max-Min Residual Capacity Routing (MMRCR)–Compute routing cost based on traffic dependent metric that is a function of probability of successful transmission and interference•Least Resistance Routing (LRR)–Routing cost is a function of interference, accounting for both other radio transmission and jamming11Link Connectivity and Route Calculation•Network information stored in–Neighbor table–Tier table–Device table•Neighbor table–Broadcast a Packet Radio Organization Packet (PROP) every 7.5 seconds»Neighbors that hear a PROP make entry in their neighbor tables»When nodes hears a PROP, it updates its neighbor table»Transmitted data packets also used to build neighbor table–Also tracks bidirectional quality of links with neighbors (retransmission counts)12Link Connectivity and Route Calculation•Tier Table–Every packet radio knows the “best” next node on the route from it to a given destination node–Tier 1 = 1 hop neighbors–These neighbors send out their PROPs indicating that they are one hop from the originator»At next step, receivers of these PROPs know that they are 2 hops away from the originator»Process continues until every radio knows its distance in tiers from every other radio–“Best”: shortest route with “good” connectivity»To change table, must discover a new node with better link quality and lower tier number than currently recorded next node–Also disseminate information about bad links in PROP messages13Link Connectivity and Route Calculation•Device Table–Logical addressing: maps device to a packet radio–Information about the radio’s attached device is included in PROP messages–This allows new radios to be attached to devices and vice versa–Such correspondences are maintained in the device table at each packet radioPNMLQ1 2DevicePR
View Full Document
Unlocking...