RFC 2009
GPS-Based Addressing and Routing
RFC 2009: GPS-Based Addressing and Routing 🦋
okay bestie, this one is from November 1996 and it's an Experimental doc 🧪 It's from the Network Working Group, written by T. Imielinski and J. Navas at Rutgers University. The title block doesn't list anything it obsoletes or updates, so it's standing on its own 💅
Status of This Memo 🌸
this memo defines an Experimental Protocol for the Internet community 🧪 it does NOT specify an Internet standard of any kind, so don't treat it like one. they're asking for discussion and suggestions for improvement, and the memo can be distributed with no limits 📬
IANA Note 🎀
this doc describes a possible experiment with geographic addresses 🗺️ it uses some specific IP addresses and domain names as examples so the concepts are easier to picture. but these addresses and names are NOT registered, assigned, allocated, or delegated to the use suggested here. so don't go grabbing them, iykyk 🙈
Table of Contents 💜
1. Introduction...................................... 2
1b. General Architecture...................... 3
1c. Scenarios of Usage: Interface Issues...... 3
2. Addressing Model.................................. 4
2a. Using GPS for Destination Addresses....... 5
3. Routing........................................... 7
3a. GPS Multicast Routing Scheme (GPSM)...... 7
3a-i. Multicast Trees................... 8
3a-ii. Determining the GPS Multicast
Addressing........................ 10
3a-iii. Building Multicast Trees.......... 11
3a-iv. Routing........................... 12
3a-v. DNS Issues........................ 12
3a-vi. Estimations....................... 12
3b. "Last Mile" Routing..................... 13
3b-i. Application Level Filtering....... 13
3b-ii. Multicast Filtering............... 13
3b-iii. Computers on Fixed Networks....... 14
3c. Geometric Routing Scheme (GEO)........... 14
3c-i. Routing Overview.................. 14
3c-ii. Supporting Long-Duration GPScasts. 16
3c-iii. Discovering A Router's Service Area 17
3c-iv. Hierarchical Router Structure and
Multicast Groups.................. 18
3c-v. Routing Optimizations............. 19
3c-vi. Router-Failure Recovery Scheme.... 19
3c-vii. Domain Name Service Issues........ 20
4. Router Daemon and Host Library.................... 21
4a. GPS Address Library - SendToGPS()......... 21
4b. Establishing A Default GPS Router......... 22
4c. GPSRouteD................................. 22
4c-i. Configuration...................... 23
4d. Multicast Address Resolution Protocol (MARP) 23
4e. Internet GPS Management Protocol (IGPSMP). 24
5. Working Without GPS Information................... 25
5a. Users Without GPS Modules................. 25
5b. Buildings block GPS radio frequencies
What then?................................ 25
6. Application Layer Solution........................ 25
7. Reliability....................................... 26
8. Security Considerations........................... 27
9. References........................................ 27
10. Authors' Addresses................................ 271. Introduction ✨
okay so in the near future GPS is gonna be everywhere 📍 and that opens the door to a whole bunch of location-based services like directions and navigation 🧭 this doc proposes a family of protocols and addressing methods to plug GPS into the Internet Protocol so you can build those services. examples include:
- Multicasting selectively, but only to specific geographical regions defined by latitude and longitude 🚨 like sending an emergency message to everyone who is currently in a specific area, such as a building or train station.
- Providing a given service only to clients who are within a certain geographic range from the server (which may be mobile itself), say within 2 miles.
- Advertising a given service in a range-restricted way, say, within 2 miles from the server.
- Providing contiguous information services for mobile users when the information depends on the user's location 🗺️ in particular, location-dependent bookmarks that give the user any important info that happens to be local (within a certain range), possibly including other mobile servers.
the solutions here are flexible (scalable) in terms of the target accuracy of the GPS 💅 and they also talk about what to do when GPS just can't be used, like inside buildings 🏢
the big challenge is fitting the idea of physical location into the current Internet, which runs on logical addressing 🧠 they see three general families of solutions:
a) Unicast IP routing extended to deal with GPS addresses b) GPS-Multicast solution c) Application Layer Solution using extended DNS
the first two are presented in this memo, and the third one only gets a quick sketch 🎀
1b. General Architecture 🏗️
we're assuming a general cellular architecture with base stations called Mobile Support Stations (MSS) 📡 the cells can be all kinds, outdoor and indoor. they'll talk about both cases: when the mobile client has a GPS card in their machine, and when the GPS card doesn't work (i.e. - inside buildings) 🙈
each MSS covers a cell with a well-defined range, specified as a polygon of spatial coordinates, and the MSS knows its own range 💜
1c. Scenarios of Usage and Interface Issues 🌈
here are some scenarios for geographic messaging, and they're honestly so good 😭
picture a patch of land next to a river 🌊 during a severe rainstorm, local authorities might want to send a flood warning to everyone living within a hundred meters of the river.
for the interface, they propose a zoomable map, similar to the U.S. Census Bureau's Tiger Map Service 🗺️ the map lets a user look at an area at different magnifications. then they use a pointing device, like a mouse, to draw a bounding polygon around the area that should get the message. the computer translates the drawn polygon into GPS coordinates and uses those when sending and routing the message. regions drawn on this zoomable map can be stored and recalled later too. honestly it's kind of like the address books in a lot of email programs 📇
back to the flood example: officials pull up a map with the river that's in danger of overflowing. they hand-draw a bounding polygon around all the areas at least a hundred yards from the river 🫶 that polygon becomes the destination for a flood-warning email to everyone in the area, and then the warning gets sent. other uses include traffic management (like reaching vehicles that are stuck in traffic 🚗) and security enforcement 👮
there are also general client-server apps where servers get picked by geographic distance. like, you might want to find all the car dealers within 2 miles of you 🚘 this is a twist on the Web idea, where location and distance matter when picking information. they're currently working on location-dependent bookmarks (hot lists), where pages from static and mobile servers within a certain distance of the client show up on the client's screen ✨
2. Addressing Model 💅
two-dimensional GPS positioning gives you latitude and longitude as a four-dimensional vector 🧮
<Direction, hours, minutes, seconds>where Direction is one of the four basic values: N, S, W, E. hours ranges from 0 to 180 (for latitude) and 0 to 90 for longitude, and finally, minutes and seconds range from 0 to 60 ⏰
so <W, 122, 56, 89> is an example of longitude, and <N, 85, 66, 43> is an example of latitude 📍
four bytes of addressing space (one byte per dimension) is needed to store latitude, and four bytes is also enough to store longitude 🧠 so eight bytes total can address the whole surface of the earth with precision down to 0.1 mile!! 🤯 and if you want precision down to 0.001 mile (1.8 meters), you'd need five bytes for each component, so ten bytes together for the full address (as military versions do) 🫡
the future version of IP (IP v6) will definitely have enough bits to give an address to even smaller GPS-addressable units 🔮 but in this proposal they assume the current version (IP v4) and make sure they manage the address space more economically than that 💜 the smallest GPS-addressable unit they call a GPS-square 🟦
2a. Using GPS for Destination Addresses 🎯
a destination GPS address can be represented by one of the following:
- Some closed polygon, such as:
circle( center point, radius )
polygon( point1, point2, point3, ... , pointn)where each point is expressed using GPS-square addresses. this notation sends a message to anyone within the specified geographical area defined by the closed polygon 🔥
- A site-name as a geographic access path
this notation basically copies the postal mail service 📮 you send a message to a specific site by specifying its location in terms of real-world names, like the name of a specific site, city, township, county, state, etc. this format uses the directory service detailed later on 📖
for example, if we were sending a message to city hall in Fresno, California, we could do it with either a bounding polygon or the mail address 🏛️ if we go with a bounding polygon, we specify the GPS limits of the city hall as a series of connected lines that form a closed polygon around it. since we've got a list of connected lines, we just have to record the endpoints of the lines 🧵 so the address of the city hall in Fresno could look like:
polygon([N 45 58 23, W 34 56 12], [N 23 45 56, W 12 23 34], ... )or, since city hall in Fresno is a well-defined geographical area, it's simpler to just name the destination 🎀 that's done with a "postal-like" address such as city_hall.Fresno.California.USA
and for "ad hoc" areas, like a quad between 5th and 6th Avenue and 43 and 46 street in New York, the polygon addressing is what gets used 🗽
Okay bestie, so the big problem is that the IP address space is kinda small 😭, so we can't give every GPS square its own address 💀. The fix is to make the smallest addressable units flexible: less address space means bigger atoms 🫶. We can still be super precise inside the message body, since the space limits only apply to the IP addressing part ✨.
By a geographic address we just mean an IP address that belongs to a geographic area or point of interest 🗺️. Our solution is flexible about how much geographic address space we use 💅.
Here are the two terms you need, and they're giving main character energy 👑:
- Atoms: the smallest geographic areas that have a geographic address. They could be as tiny as GPS squares, but they can also be bigger 🧩.
- Partitions: larger geographic areas that also have a geographic address. A state, a county, a town, etc. can be a partition, and a partition holds a bunch of atoms 🌈.
Some possible atoms and partitions are:
- A rectangle, made by truncating the longitude or latitude part of a GPS address and skipping one or more least significant digits 🎀
- A circle centered on a specific GPS address with a prespecified radius 🦋
- Irregular shapes like administrative domains: states, counties, townships, boroughs, cities, etc. 🏙️
So partitions and atoms (which are obviously special atomic partitions 🤓) get geographic addresses that routers use 🛣️. Areas that are smaller than an atom, or that have an "irregular shape", won't get a geographic address, so the application layer has to handle them 🫠.
3. Routing ✨
Let's talk about how a message finds its way to any geographic destination 🧭.
We split the connection from sender to receiver into two legs 🦵: the first leg goes from the sender to the MSS (base station), and the second leg goes from the MSS to the receiver who lives in its cell 🏠. Our two solutions are different on the first leg, but they use the same options for the second leg, which we call "last mile" 💖.
3a. GPS-Multicast Routing Scheme 🌸
Here we cover the first leg, from the sender to the MSS, and we start with the multicasting solution 📡.
Every partition and atom gets mapped to a multicast address. The exact form of that mapping comes later in this subsection, but first here's the basic vibe 🦋.
This solution is a flexible mix of multicast and application-level filtering for geographic addressing 🫶. The key idea is to approximate the addressing polygon with the smallest partition that contains it, then use the multicast address of that partition as the IP address of the message 🎯. The original polygon lives in the packet's body, and the exact matching happens at the application layer on the second leg 💅.
So how does multicast routing actually work? 🤔
3a-i. Multicast Trees 🌳
The basic idea for the first level of multicast routing is that each base station joins the multicast groups for every partition that intersects its range 🫧. That means the MSS isn't only aware of its own range, it also has complete info about the system-defined partitions its range intersects 🧠. It can get this info when the MSS is installed, from the geographic database stored as part of DNS 🌐.
If the proper multicast trees are built (for example, using a link state multicast protocol) ✨, then the sender can just work out the multicast address of the partition covering the original polygon they want to send to, use that address on the packet, and put the original polygon spec into the packet content 💌. That way multicast makes sure the packet reaches the proper MSS 🎀.
Example
For instance, the MSS in New Brunswick might have its range intersect these atoms and partitions: the Busch, College Avenue, Douglass, and Livingston Campuses of Rutgers University (atoms) 🎓, the New Brunswick downtown area (an atom) 🌆, the Middlesex county partition 🍓, and the NJ state partition 🦀. Each of these atoms and partitions gets mapped to a multicast address, and New Brunswick's MSS has to join all of those multicast groups 🫶.
Here's how the message gets specified and sent 💕:
The user grabs a map of the New Brunswick area, maybe from DNS extended with the relevant maps 🗺️. They specify the destination by drawing a polygon on the map, which gets translated into a sequence of coordinates 🖍️. At the same time, the polygon gets "approximated" by the smallest partition that contains it 🧩. The multicast address for that partition becomes the IP address for the packets carrying the message, and the exact destination polygon sits in each packet's body 📦. So the packet gets delivered with multicast routing to the set of MSS that are members of the specified multicast group (basically, every MSS whose range intersects the given partition) 🚀. Each of those MSS then follows the "last mile" routing that's described in detail later in the proposal 🦵. Briefly, the MSS can multicast the message further on that same multicast address, and the client does the final filtering at the application layer by matching its GPS location with the polygon in the packet's body 🎯. Other solutions based entirely on multicasting are also possible, as described below 🦋.
End_Example
BUT 😭 things can't be as simple as that. With such a huge potential number of multicast groups, if we built entire multicast trees, the routing tables could get way too large 📈💀. Luckily, we don't need complete multicast trees 🙌. It's not important to know the precise location of every atom in California from somewhere far away, like NJ 🤷♀️.
So we modify the simple solution with this intuition 💡:
The smaller the partition (atom) is, the more locally its information gets propagated 🫧.
So only multicast group membership for very large partitions gets propagated across the whole country 🇺🇸.
For example, a base station in Menlo Park, California can intersect several atoms and several larger partitions that cover Menlo Park 🌴. Those could be a partition covering the entire San Mateo county, the next one covering the entire state of California, and finally one covering the entire West Coast 🌊. This base station has to join the multicast groups for all of these rectangles 📡. But only the info about the West Coast partition's multicast group gets propagated to the East Coast routers 🗽.
Now, a simple address aggregation scheme where only a "more significant portion" of the address propagates far away would NOT work 🙅♀️. Why? Because a remote router, say in NJ, could end up with several aggregate links leading to California. In the worst case, all of its links could point to California, since it might have received routing info for some location in California on any of those links 😱.
To avoid this, each partition has one or a few MSS that act as designated router(s) for it 👑. For example, the California partition might have only three designated routers: one in Eureka, one in Sacramento, and one in LA 🌵. Only routing entries from the designated routers get aggregated into the aggregate address for California. Information coming from other city routers gets dropped and isn't aggregated at all 🗑️. Together with the standard selection of shortest routes, this limits how many links lead to an aggregate address 🔗. When there's only one designated router per partition, there's only one aggregate link in any router. This might lead to non-optimal routing, but it solves the problem of redundant links 🫶.
Even with designated routers, the same packet can still arrive at a given base station more than once, because of different alternative routes 🔁. So a proper mechanism for discarding redundant copies of the same packet should still be in place 🧹. Honestly, because base station ranges can intersect, receiving redundant copies of the same packet is always possible and has to be handled as part of any solution 💀.
3a-ii. Determining the Geographic Multicast Addressing 🧭
Let's get into the specifics: the proposed addressing scheme and the routing that goes with it 🤓.
The addressing is hierarchical 🪜. Here's the convention: each multicast address for a partition or an atom has the following format 💖:
1111.GPS.S.C.xGPS is the specific code for the geographic addressing subspace of the overall multicast addressing space 🌈. The S, C, and x parts work like this 💅:
- S: the encoding of the state. Each state partition gets the address
S/0/0🗺️. - C: the county within a state. Each county partition has the address
S/C/0🏘️. - x: the atom within a county 🧩.
Here the 0's are sequences of 0 bits in the positions that correspond to the "C part" and the "x part" of the address 🤍.
For example, if the GPS part is 6 bits, which gives 1/64 of the existing multicast addresses to geographic addressing, then we have 22 bits left 🧮. The S part takes the first 6 bits, the C part takes the next 6 bits (say) 🎀, and the next 10 bits encode the different atoms within a county 🫧.
So in our terminology, this addressing scheme has two types of partitions: states and counties 🗺️.
We assume the GPS network consists of all base stations (MSS) plus the rest of the fixed network infrastructure 🏗️. However, the designated GPS routers are only selected from the population of MSS 👑. Specifically, there are state-dedicated and county-dedicated routers 💜.
Here's how designation works 🫶. From the set of all MSS, only certain MSS play the role of designated routers for county and state partitions. Non-designated MSS only join the multicast groups that correspond to GPS atoms, not the GPS partitions they intersect 🙅♀️. An MSS that is a designated router for a county partition joins the multicast group of the county it's located in, but not the state 🏘️. Finally, the state designated router also joins the multicast address corresponding to the state it's located in 🌟.
3a-iii. Building Multicast Trees 🌳
okay so we assume every router has geographic info attached to it 🗺️ in the same format we use for multicast mapping, S/C/x. basically it encodes the atom that contains the router.
the multicast tree gets built when a router passes its multicast memberships along to its neighboring routers. ✨ but a given router only keeps certain addresses, because the whole vibe is not holding onto specific info that's far away.
here's how it goes. the router at S/C/x (not necessarily an MSS based router) only keeps addresses about S'/0/0 and S/C'/0, where S' and C' are different from S and C, plus S/C/x for all x. so it drops every address of the form S'/C'/y for all S' different from S, except the ones with C'=0 and y=0. it also drops every address of the form S/C'/y with C' different from C, except the ones with y=0. 💅 those dropped addresses won't get forwarded any further either.
notice that only info from designated routers gets forwarded further away, bc non-designated routers aren't allowed to join the multicast groups that match the states and counties. 🙈 so their multicast membership info won't be propagated at all.
this means a router at S/C/x won't bother about specific spots within S'/C'/y, since those are "too far" away. 🧚
also, this service might not be provided everywhere, so we may not have to use every multicast address, even the ones assigned for geographic addresses. 🌸
and everything here is flexible! ✨ if we have more multicast addresses available (IP v 6), we get more precise addressing because the atoms are smaller. 🦋
3a-iv. GPS Routing 📍
okay the routing rule is this 👑. given a packet, we always look for the "closest" match in the routing table.
- if there's a complete match, we follow that link. 💖
- if there isn't one, we follow the address with the x-part zeroed out (the county address).
- if there's none with a county that agrees with the destination county, we look at the entry that agrees with the state part of the destination address.
that's the whole algorithm bestie, it's giving clean but also a little bit of a fallback chain 🥹
3a-v. DNS Issues 🎀
so how does the client even find out the multicast address the packet should be sent on? 🤔 we assume the local name server has the complete state/county hierarchy, and that each county map can come with the "grid" of atoms and partitions already clearly marked. 🗺️✨
points of interest within a county can also be attached a multicast address, just like atoms. then a given base station would have to join the multicast groups for the points of interest that it covers. 📡
the final stage is for the receiver to look at the polygon (point of interest) encoded in the body of the multicast packet, and then decide based on its own GPS location whether to receive the packet or not. 🫶 doing this on the application layer simplifies a lot of routing issues, but there's a tradeoff, especially when we have very short S/C/x addresses. base stations that don't actually cover the given polygon can get reached unnecessarily. 😭 this may happen, and we need to figure out how many multicast addresses are necessary to reduce these "false" alarms to the minimum. 🔥
3a-vi. Estimations 🧮
let's do the math! 💜 assume an average cell size of, say, 2km x 2km, and an average state size of, say, 200,000 square km, and an average county size of, say, 4,000 square km.
a reasonable size for the atom is around the size of the cell, because then we don't hit wrong cells too often. 🍓
so we need the x addressing part of the S/C/x to encode 4,000/4 cells: 1.000 atoms. ✨ that means we need 10 bits for the x part. with 6 bits for the state and 6 bits for the county, that gives 22 bits total, which is 1/64 of the total IP v4 multicast addressing space. 💀 iconic.
and with IPv6 we'll have, of course, way more addressing space that we can use for GPS multicast routing. 🌈
3b. "Last Mile" Routing
okay so bestie, the last mile is where things get personal 🫶 Multicasting is gonna handle last mile routing in BOTH of our solutions (the one we just covered and the geometric routing one coming up next), just in different ways 💅
3b-i. Application Level Filtering
the MSS will forward the geographic message on its wireless link under a multicast address 📡 This multicast address will either be the same for every location in the range of the MSS's cell, OR there will be several addresses, one for each atom that intersects the given cell 🧚 Then a complete GPS address (like a polygon) gets put in the body of the packet, and the exact address matching happens at the application layer 💜 The receiver knows its own GPS position and uses it to match against the polygon address. It can get that position either from the GPS card or, if it's indoors, from the indoor base station, which knows its own GPS position from a configuration file 🌸
3b-ii. Multicast Filtering
in multicast level filtering, the base station assigns a temporary multicast address to the addressing polygon in a message 🦋 It sends out a directive on the cell's specially assigned multicast address. All mobile clients who live in that cell are members of that special multicast group (one per MSS) 💖 The directive from the MSS contains the pair of the temporary multicast address together with the polygon. To make it more reliable, this message gets multicast several times 🔁 The clients, knowing their GPS positions, will then join the temporary multicast groups if their current locations are inside the advertised polygon ✨ Then the MSS sends the real message out using the temporary multicast address 🎀
The temporary multicast address gets cached for a period of time. If more packets for the same polygon show up in a short window, they go out on the same multicast address. If not, the multicast address is dropped and purged from the cache 🫧 Filtering on the client's station then happens entirely at the IP level 🖥️ This solution adds some extra delay (you need time to join the temporary multicast group), BUT it cuts down on the irrelevant packets the client gets 🙈 This is especially important for very long messages 📜
3b-iii. Computers on Fixed Networks
fixed-network computers should also monitor all of the mandatory multicast addresses for their site and GPS square 👑 That way, fixed computers also get messages sent to specific GPS addresses 💅
Modified base stations would still be in charge of multicasting the messages to the computers 📮 These base stations would have the same GPS-routing functionality as the mobile computer base stations 🌈 The main difference is that mobile computer base stations use radio frequencies to multicast their messages, while fixed network base stations use the local Ethernet or Token Ring network 🔌
The next scheme only differs from the GPS multicast scheme above on the first leg of the route, from the sender to the MSS 🚀 The "last mile" from the MSS to the final destination has the same options as described above 💫
3c. Geometric Routing Scheme (GEO)
the Geometric Routing Scheme (GEO) uses the polygonal geographic destination information in the GPScast header directly for routing 🗺️ GEO routing is going to be implemented in the Internet Protocol (IP) Network layer, kind of like the way multicast routing was first implemented 🦋 Basically, a virtual network that uses GPS addresses for routing gets overlaid onto the current IP internetwork 🕸️ We'd do this by creating our own GPS-address routers 🏗️ These routers use tunnels to ship data packets between each other and between the routers and base stations 🚇
3c-i. Routing Overview
sending a GPScast message involves three steps: sending the message, shuttling it between routers, and receiving it 📬
Sending a GPScast message is very similar to sending a UDP datagram 💌 The programmer calls the GPScast library routine SendToGPS(). Among other parameters, this routine accepts the GPS polygonal destination address and the body of the message 💜 SendToGPS() encapsulates the GPScast message in a UDP datagram and sends it to the class E address 240.0.0.0. Before that, the system administrator specifies a route command in /etc/rc.local or /etc/rc.ip so that packets addressed to 240.0.0.0 get sent to the address of the local GPS router instead 🧚 That way the datagram goes to the nearest GPS router 🎯
Before we get into how GPS routers shuttle the message to its destination, we need a quick intro to routers and their parts 🤓 For scalability, GPS routers are arranged hierarchically 🪜 Each layer corresponds to a distinct geographic area, like a state or a city 🌆 At the top are country-wide routers that move messages from one end of the country to the other 🇺🇸 At the bottom are campus or department routers that move messages between the base stations 🏫 See Figure 1 👀
Country-Router(s)
/ \
State-Router(s)
/ \
City-Router(s)
/ \
Router Router
/ | \ | \
Base Base Base Base BaseFigure 1: Hierarchy of routers.
A GPS router basically has three parts: a service area table containing the geographic area serviced by the router and each of its hierarchical children, a hashed cache of previous actions, and a table containing the IP addresses of at least the router's children and the router's parent 🧠 For a bottom-layer campus router, the service area table contains polygons describing the geographic reach of each child base station's cell 🗺️ The polygon made from the union of all of the router's child base stations' polygons defines the router's service area 💖
Once the datagram arrives at a GPS router, the router strips the datagram off, leaving it with the original GPScast message 🎁 First, the router has to figure out whether it services any part of the destination polygon's area 🔍 To do this, it finds the intersection between the destination polygon and the polygon describing the router's service area 🧩 The polygon intersection algorithm is described by O'Rourke in his paper, A New Linear Algorithm for Intersecting Convex Polygons 📄 This algorithm requires order N-squared time in the worst case 🐢 If the intersection result is null, the router simply sends the message to its parent router 🫡
------ Destination Polygon
| A |
--------------
| | B | | Router's Service Area Polygon
--------------
| C |
------Figure 2: Polygon Difference
However, if the result is NOT null, then the router does service the area described by the intersection polygon 🔥 The router now subtracts its service area from the destination polygon and sends the rest to its parent router 💅 This subtraction step is actually a by-product of the intersection algorithm 🧁 Using the example in Figure 2, the destination polygon and the router's service area polygon intersect at the region labeled B 🎯 So the router subtracts out the B section and sends the remaining sections A and C to its parent router 🦋
Continuing with the example, the router now uses the intersection polygon B to figure out which base station (or stations) will receive the GPScast message 🔭 The router finds the intersection between region B and the polygon of each base station's cell 🧩 Those base station polygons that intersect region B will be sent the GPScast message 📨 Processes on Mobile Hosts served by these base stations will then use the routine RecvFromGPS() to receive the GPScast message 📲✨
3c-ii. Supporting Long-Duration GPScasts ✨
Okay so here's the thing, bestie 🎀. We're probably gonna need to support sending real-time continuous media to a GPS destination, like an audio GPScast or a video GPScast 🎧📹. That means jitter has to be reduced or the audio and video playback gets super glitchy 😭. Checking the destination geometry of every single packet would add unnecessary delays and could make jitter worse, so ngl, that's a no-go 🙅♀️.
So the router is gonna keep a hashed cache of the latest GPScast packets and their destinations 💅. Each cache item gets hashed using the Sender Identification from the header of GPScast messages as the key 🔑. Each cache item holds a time stamp and a list of the next hops for that GPScast. When the time stamp goes past a certain limit, the cache item gets dropped 🗑️. The list of next hops is basically the IP addresses of the base stations, peer routers, and parent router that are supposed to get a copy of the GPScast messages 🦋.
When a router gets a GPScast packet, it uses the incoming packet's Sender Id as a key into the hashed cache 🔍. If it's NOT the first packet for this destination and the timer on the hash table entry hasn't expired yet, the cache hands back a list of all the destination addresses that copies of the packet must be sent to 🌸. Copies go out to all of those destinations and the hash entry's time stamp gets updated ⏰.
If no hash table entry is found (aka this is the first packet for this destination address), then the normal geometry checking routine takes over 🧮. A new cache entry is made recording all of the next-hop destination addresses of the GPScast 📝. This is giving efficiency, because if several other packets with the same GPS destination follow that first one, the router can just look up the destination base stations in the hash table instead of doing the geometry math again 🧚✨.
3c-iii. Discovering A Router's Service Area 🗺️
When the router starts up, it checks its configuration file 📂. One of the things it finds in there is the multicast address of the base station group that all of its child base stations are members of 🫶. The router joins this group and then sends out Service Area Query messages to this multicast group periodically, to discover and refresh what it knows about its children base stations and the geographical areas they service 🔄.
Queries go out infrequently (no more than once every five minutes) so the IGPSMP overhead on the network stays super low 🌙. BUT, since the query is sent using unreliable multicast datagrams, some base stations might not get it 😬. This matters in two cases: when a child node fails and when a router first boots up. The failed child case gets explained later 👀. When a router first boots up, though, it can send several queries in a short amount of time to make sure base stations receive one and to build up its knowledge of its child base stations quickly 🚀.
Base stations respond to a Service Area Query by sending a Service Area Report 📨. The report goes out on the same multicast group address that all the base stations have joined, and it contains the base station's geographical service area 🗺️. To avoid a sudden flood of reports all hitting at once, each base station starts a random delay timer, and it only sends its report when that timer expires ⏳.
For every base station that responds, the router creates an IP tunnel between itself and that base station 🚇. This tunnel carries the GPScast packet traffic between the base station and the router 💖. Each responding base station and its geographic area of service also goes into the router's geometric routing table as a possible destination for GPScast packets 📍. Any base station that doesn't respond to ten continuous Service Area Queries is considered unreachable and gets dropped from the routing table 💀.
3c-iv. Hierarchical Router Structure and Multicast Groups 👑
R5----------------------R6
/ \ / \
R1---------R2 R3---------R4
/ | \ / | \ / | \ / | \
b1 b2 b3 b4 b5 b6 b7 b8 b9 b10 b11 b12Figure 3: Two peer routers (R5 and R6) cooperatively servicing four child routers (R1 - R4).
For scalability, the network uses a hierarchy of routers to carry messages from a sender to a receiver 🌈. Each layer of peer routers gets its own multicast group address for swapping Service Area Queries and Reports between the peer routers 🎀. Routers in different subtrees don't need to know about routers in other subtrees, so the multicast group addresses also differ between hierarchy subtrees 🙈. Check out figure 3 🦋. For example, routers R1 and R2 share a multicast group and know about each other 💅. At the same time, routers R3 and R4 share a different multicast group and know about each other 🫶. But R1 and R2 do NOT know about R3 and R4, and vice versa 🤷♀️.
But how does the router know where its peer routers are, how many there are, and who its parent router is? 🤔 Like we said before, the router checks its configuration file on start-up 📂. That file includes the address of its parent router and the multicast group address that the peer routers will use 💜. This peer multicast group address works the same way as the base station multicast group address 🔁. It's used to send and receive Service Area Queries and Reports between the parent router and the peer routers 📡. There's only one difference: when a router sends a Service Area Report, in addition to its geographical service area, it also includes the multicast address of its children base stations 🧚. The reason for this is explained in the router-failure recovery scheme below 👀.
3c-v. Routing Optimizations ⚡
This optimization tries to reduce the latency of a GPScast 🏃♀️. It does this by cutting down the number of hops a packet has to travel before it finds its destination 🛣️. The idea is: instead of going to the parent router and then over to the sibling, just go to the sibling directly 🙌. Bonus, this also stops the parent router from becoming a bottleneck or a single point of failure 🫶.
With this optimization, when a router figures out who gets the GPS packet, it treats its peer routers as if they were also its children in the routing hierarchy 👯♀️. So the router's service area becomes the union of the service areas of its children and its peer routers 🗺️. And when the destination polygon intersects the router's service area polygon, the router forwards a copy of the GPScast packet to any child or peer router whose geographic service area contains or touches the packet's GPS destination polygon 📦.
BUT before it sends a copy to a peer router, it first finds the polygon:
P = D /\ Swhere D is the packet's destination GPS polygon, S is the polygon for the service area of the peer router, and P is the polygon for the intersection of D and S 🧩. The polygon P gets swapped in for the destination polygon D in the packet, and only then is the packet forwarded to the peer router 🔄. This is necessary because the peer router uses that same routing algorithm 🤖. So if the peer router got a packet with the original destination polygon D, it would also route copies of the packet to all of its qualifying peer routers, and you'd get a chain of packet copies bouncing back and forth 😱🏓.
3c-vi. Router-Failure Recovery Scheme 🛟
When a router fails, the system should be able to route around it and keep servicing GPScast messages 💪. Detecting whether a router has failed is the parent router's job 👑. Using Figure 3 as the example hierarchy, the parent router R5 periodically sends out Service Area Query IGPSMP messages on its children's multicast group address 📣. So the child routers R1 and R2 both receive this query 👯♀️. Normally both routers respond with a Service Area Report message 📨. That message contains a polygon describing their service areas and the multicast group address of their children 🗺️.
BUT if a router, R1, doesn't respond to ten continuous queries, it MUST be considered to have failed 💀. Once R5 detects this, it sends a Set Service Area message to the child router R2, telling it to take responsibility for the base stations underneath the failed R1 router 🫡. In this Set Service Area message, the parent router includes the multicast group address of R1's children 🧩. R2 uses that multicast address to learn the service areas and IP addresses of R1's children 🔍. Then R2 issues a Service Area Report advertising its new, enlarged service area responsibilities 📢. All peer and parent routers then update their routing tables to include this new info 🔁. When the failed router, R1, restarts, it declares that it's alive and that it's servicing its area again 🌅. All routers then update their routing tables again 💅.
In the case where there's no parent router, like at the top of the routing hierarchy, each peer router keeps track of its neighbors 🫂. If a neighbor router fails, the first neighbor router to declare that it's taking over the base stations for the failed router takes responsibility 🥇. The rest carries on as before 💖.
3c-vii. Domain Name Service Issues 🌐
Domain Name Servers (DNS) could be used to make GPS geographic addressing easier for sites of interest 📍. The goal is to describe specific geographic sites in a more natural, real-world way, using a postal-service-like addressing method 📮. Basically, the DNS would resolve a postal-style address, such as City_Hall.New_York_City.New_York, into the IP address of the GPS router responsible for that site 🏛️. The GPS router would then route the message to all available recipients at the site 📬.
The DNS gets used when a message is sent using the addressing scheme below 💌:
site-code.city-code.state-code.country-codeThe DNS evaluates the address in reverse, starting with the country code, then the state code, and so on 🔙. This is the same method the IP DNS service currently uses to return IP addresses based on country or geographic domains 🌍✨.
- Router Daemon and Host Library 🧚💅
4a. GPS Address Library - SendToGPS() ✨
okay so bestie, we're building a whole GPS address library 🗺️🫶 the main routines are SendToGPS() and RecvFromGPS(), and they're giving main character energy. here's the sending one:
SendToGPS(int socket, GPS-Address *address, char *message, int size)where socket is a datagram socket you already made 🧦, address is a filled-in GPS-Address structure, and message and size tell it what the actual message is and how big it is. it's literally that simple 💅
here's what a GPS-Address looks like:
typedef _GPS-Address {
enum { point, circle, polygon } type;
char *mail-address;
struct
{
enum { North, South, West, East } dir;
int hours, minutes, seconds;
} *points;
} GPS-Address;so SendToGPS() takes your GPS-addressed message, wraps it up in an IP packet, and sends it off like a normal IP datagram. ngl the wrapping is so iconic 🎀 it goes like this:
--------------------------------------------------------
| IP Header with destination address set to 240.0.0.0 |
--------------------------------------------------------
| Sender Identifier |
--------------------------------------------------------
| Address Type - Circle|Polygon |
--------------------------------------------------------
| Actual GPS Address (see below) |
--------------------------------------------------------
| Body of Message |
--------------------------------------------------------the Sender Identifier is a combo of the sender's process id 🪪, the host's IP address 🏠, and the center of the destination polygon 📍. and the Actual Address is one of these two vibes:
circle- a single GPS address plus a range, measured in centiminutes 🎯polygon- a list of GPS addresses that ends with the impossible address:N 255 255 255💀 (it's the bestie that tells you the list is over)
and now the receiving side 📥 RecvFromGPS() looks like this:
RecvFromGPS(int socket,GPS-Address *address,char *message,int size)where socket is a datagram socket you already made, address is an empty GPS-Address structure, and message and size describe the message buffer and its size 🧺
4b. Establishing A Default GPS Router 🏡
okay so the default GPS router is found using the unicast routing table that lives in the UNIX kernel 🧠 the local system administrator is supposed to have already set that table up so that all GPScast messages get sent to the local GPS router 📬 but if there's no route for GPScast messages in the table, then everything just goes to the default gateway by default 🚪 and if that default gateway doesn't support GPScast messages, then every single GPScast attempt is going to return an error 😭
by default, every GPScast message starts out with the destination set to the class E address 240.0.0.0 ✨ the system administrator adds a route to the kernel routing table for this address, and that route says where the local GPS router is 🗺️ the route command is what changes the routing table, and it can go in /etc/rc.local or /etc/rc.ip so it takes effect every time the computer boots 🔄 for example, to say that GPScast messages addressed to 240.0.0.0 should by default go to the router sitting on a computer on the same subnet with local address 128.6.5.53, you'd use this:
/etc/route add host 240.0.0.0 128.6.5.53 0⚠️ bestie, careful here: if the default destination for GPScast messages is a host that doesn't support GPS addressing, then any process trying to route GPScasts through that host gets Network Unreachable errors 🙈
4c. GPSRouteD ✨
Okay bestie, so to get GPS address routing working across an entire IPv4-based internetwork, we're building special-purpose routers called GPSRouteD 💖. These routers are gonna support GPS address routing on top of the current Internet, and they're the main characters of this whole setup 👑.
GPSRouteDs connect to each other using virtual point-to-point links called tunnels 🦋. A tunnel runs over regular unicast networks and links two GPSRouteDs together. Here's how it slaps: the tunnel wraps each GPS address message inside an IP datagram, then sends it to the host on the other end. So every IPv4 router in between sees GPS messages that look like totally normal unicast packets 🫶. At the far end, the receiving GPSRouteD unwraps the GPS address message from the datagram and keeps the routing process going 💅.
Tunnels are honestly iconic because they let the GPS routers form a virtual internetwork across the current Internet without caring about the physical properties of the networks underneath 🌈. The host running the router daemon also doesn't need to be connected to more than one subnet in order to forward GPS messages, which is so convenient 🎀. This virtual internetwork is only responsible for routing GPS address messages, nothing else 🧚. And ngl, it's not meant to be a permanent solution. It's just a way to support GPS address routing until it gets wider acceptance and support in the Internet infrastructure ⭐.
4c-i. Configuration
When a GPSRouteD first executes, it checks the file /etc/GPSRouteD.conf for configuration commands that add tunnel and multicast links to other GPS address routers 🍓. There are two kinds of configuration commands:
multicast <multicast-address> <peer|child>
tunnel <local-addr> <remote-addr>
<parent|peer|child|host> <service-area>The tunnel command creates a tunnel between the local host where the GPSRouteD runs and a remote host where another GPSRouteD runs. Heads up, bestie: the tunnel must be set up in the GPSRouteD.conf files at both ends before it will be used 🙈.
The multicast command tells the router which multicast addresses to join 💜. These addresses carry IGPSMP messages and replies. The router uses those IGPSMP messages to build up and keep its own internal routing table fresh and current ✨.
4d. Multicast Address Resolution Protocol (MARP) 🌸
Okay but this begs the question: how do the individual computers know which multicast addresses to join? 🤔 For example, an MH would have to join the multicast address of its current cell so it can receive GPScast messages (using application-level filtering), or receive directions to join other multicast groups (using multicast filtering) 🫶.
Enter MARP, the Multicast Address Resolution Protocol 💅. It works the same way as RARP, the Reverse Address Resolution Protocol. The difference is that instead of returning the IP address of the MH, it returns the multicast group address of the cell the MH is currently in. Then the MH joins that multicast group. Iconic behavior 👑.
4e. Internet GPS Management Protocol (IGPSMP) 🧚
The Internet GPS Management Protocol (IGPSMP) is how GPS routers report, query, and inform their router counterparts about their geographical service areas 💖. IGPSMP also gets used to verify that routers are functioning correctly 🫶.
The IGPSMP vocabulary has six words 🌈:
- set service area - Used by the parent router to set the geographic service area of a router. This is needed in order to automatically respond to router failure or new router boot-up.
- confirm service area - Confirms that a router has received its service area.
- geographical service area query - This message is used by a router to build up its geographical routing table. It is sent to all routers on the same level.
- service area report - This message is sent in response to a query request. It contains a bounding closed polygon described using GPS coordinates, which contains the service area for the router.
- ping - This message is sent periodically to ascertain whether the router is currently functioning properly. It is usually sent by the parent router in the hierarchy tree.
- alive signal - Usually sent as a reply to the ping message. Used by a router to indicate that it is functioning correctly. It is also sent immediately after a router boots 🦋.
All IGPSMP messages get sent on an all-routers multicast address for a particular hierarchy level. The exact multicast address can be set in the router configuration file 🎀.
Also, for the GPS-Multicast routing scheme, the time-to-live value of the service area reports gets varied to control how far the information spreads 🔥. In GPS-Multicast routing, only the multicast group membership for very large partitions gets distributed throughout the country. Smaller partitions may only be distributed to neighbor routers 🍓.
5. Working Without GPS Information 🙈
5a. Users Without GPS Modules
Mobile users without GPS modules can still participate, just at a very reduced level 🌸. When an MH enters a cell, it can use MARP to discover the local multicast group for that cell or atom. As the user roams from cell to cell, the mobile host keeps track of the current cell and adds or drops the multicast groups for those cells 💜. The user's GPS address can be set to the center of the current cell ✨.
5b. Buildings block GPS radio frequencies. What then? 🏢
Each room can have a radio beacon placed on the ceiling 💅. The beacon is weak enough that it won't penetrate walls. Each radio beacon has its own GPS address associated with it, which it broadcasts 📡. When a mobile user enters a room, his MH detects the beacon and reads the beacon's GPS address. The MH's GPS address is then set to the beacon's GPS address, and the MH uses that beacon address to do any message filtering it needs 🫶. So even though his GPS module is useless indoors, the mobile user can still have a GPS address associated with him 🌈.
6. Application Layer Solution 🧚
In this section we sketch a third solution that relies more heavily on the DNS 💖.
In the application layer solution, geographic information is added to the DNS. That gives full directory information down to the level of the IP address of each base station, plus its area of coverage represented as a polygon of coordinates 🗺️.
A new first-level domain, "geographic", gets added to the set of first-level domains 🎀. The second-level domain names include states. The third level includes counties, and finally the fourth level includes polygons of coordinates, or so-called points of interest. We can also allow polygons to occur as elements of second- and third-level domains, so messages can be sent to larger areas 👑.
So a typical geographic address can look like:
city-hall-Palo-Alto.San-Mateo-County.California.geographic
or
Polygon.San-Mateo-County.California.geographic
where Polygon is a sequence of coordinates 💜.
This geographic address gets resolved in a similar way to standard domain addresses today, into a set of IP addresses of the base stations covering that geographic area 🌸. There are several possibilities here:
a. A set of unicast messages is sent to all base stations corresponding to the IP addresses returned by the DNS. Each base station then forwards the message using either of the two last link solutions: application-level or network-level filtering 🦋.
b. All the base stations join the temporary multicast group for the geographic area specified in the message. This way we may avoid sending the same message across the same link several times 🔥. So after the DNS determines the set of relevant base stations, the temporary multicast group is established, and all packets with that multicast address are sent on that multicast address ✨.
c. Only one base station, the one central to the polygon, is returned by the DNS, just like in the IP unicast solution 💅. However, that "central" base station will have to forward messages to the other base stations within the polygon 🫶.
Notice that we should distinguish between "small area" and "wide area" geographic mail 📬. "Small area" mail will be the most common, and will most likely involve just one base station, which favors a simple form of solution (a) 🌈.
7. Reliability 💅
Should the geographic messages be acknowledged? 🤔
Since we have no control over whether users are present in the target geographic area where the mail is distributed, we don't see a need for individual acknowledgments from the message recipients 🙈. However, we believe that the base stations (MSS) covering the target area of geographic mail should acknowledge the messages 💖.
Typically only a few base stations will be involved, since we typically won't cover very broad geographic areas anyway 🌸. We assume that the base stations, in addition to forwarding the the messages on their wireless interfaces, will buffer them. They'll either periodically multicast them (emergency response), or provide them to users who just entered a cell, so those users can download the "emergency stack" of messages for that area as part of the service hand-off protocol 🚨💜.
8. Security Considerations 🔐
Some method of determining who has permission to send messages to a large geographical area is needed. For instance, perhaps only the mayor of New York City has permission to send a message to all of New York City. 😭🔥
9. References 📚
Deering, S., "Host Extensions for IP Multicasting", STD 5, RFC 1112, August 1989.
S. Deering. Multicast Routing in a Datagram Internetwork. Ph.D. Thesis, Stanford University, (December 1991).
J. O'Rourke, C.B. Chien, T. Olson, and D. Naddor, A new linear algorithm for intersecting convex polygons, Computer Graphics and Image Processing 19, 384-391 (1982).
J. Ioannidis, D. Duchamp, and G. Q. Maquire. IP-Based Protocols for Mobile Internetworking. Proc. of ACM SIGCOMM Symposium on Communication, Architectures and Protocols, pages 235-245, (September, 1991).
10. Authors' Addresses 🦋
Tomasz Imielinski and Julio C. Navas
Computer Science Department
Busch Campus
Rutgers, The State University
Piscataway, NJ
08855
Phone: 908-445-3551
EMail: {imielins,navas}@cs.rutgers.edu📦 where this page comes from
- ietf: rfc2009 1996-11
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms