idnits 2.17.1 draft-rfced-exp-navas-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Expected boilerplate is as follows today (2024-04-24) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity. ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. == The page length should not exceed 58 lines per page, but there was 2 longer pages, the longest (page 1) being 79 lines == It seems as if not all pages are separated by form feeds - found 54 form feeds but 56 pages Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an Abstract section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. == There are 1 instance of lines with non-RFC2606-compliant FQDNs in the document. == There are 14 instances of lines with non-RFC6890-compliant IPv4 addresses in the document. If these are example addresses, they should be changed. Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 229 has weird spacing: '...ic site by...' == Line 246 has weird spacing: '... Fresno is a ...' == Line 271 has weird spacing: '...graphic areas...' == Line 383 has weird spacing: '...s could be to...' == Line 398 has weird spacing: '... larger which...' == (25 more instances...) -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (March 8, 1996) is 10274 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- No issues found here. Summary: 9 errors (**), 0 flaws (~~), 10 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 INTERNET-DRAFT Expires November 1996 INTERNET-DRAFT 3 Network Working Group T. Imielinski 4 INTERNET-DRAFT J. Navas 5 Category: Experimental Computer Science, Rutgers University 6 March 8, 1996 8 GPS-Based Addressing and Routing 10 12 Status of this Memo 14 This document is an Internet Draft. Internet Drafts are working 15 documents of the Internet Engineering Task Force (IETF), its Areas, 16 and its Working Groups. Note that other groups may also distribute 17 working documents as Internet Drafts. 19 Internet Drafts are draft documents valid for a maximum of six 20 months. Internet Drafts may be updated, replaced, or obsoleted by 21 other documents at any time. It is not appropriate to use Internet 22 Drafts as reference material or to cite them other than as a 23 "working draft" or "work in progress." 25 To learn the current status of any Internet-Draft, please check the 26 "1id-abstracts.txt" listing contained in the internet-drafts Shadow 27 Directories on: 29 ftp.is.co.za (Africa) 30 nic.nordu.net (Europe) 31 ds.internic.net (US East Coast) 32 ftp.isi.edu (US West Coast) 33 munnari.oz.au (Pacific Rim) 35 Table of Contents 37 1. Introduction 38 1b. General Architecture 39 1c. Scenarios of Usage: Interface Issues 40 2. Addressing Model 41 2a. Using GPS for Destination Addresses 42 3. Routing 43 3a. GPS Multicast Routing Scheme (GPSM) 44 3a-i. GPS Rectangles 45 3a-ii. Multicast Trees 46 3a-iii. Determining the GPS Multicast 47 Addressing 48 3a-iv. Building Multicast Trees 49 3a-v. Routing 50 3a-vi. DNS Issues 51 3a-vii. Application Layer Filtering 52 3a-viii. Estimations 53 3b. "Last Mile" Routing 54 3b-i. Application Level Filtering 55 3b-ii. Multicast Filtering 56 3b-iii. Computers on Fixed Networks 57 3c. Geometric Routing Scheme (GEO) 58 3c-i. Routing Overview 59 3c-ii. Supporting Long-Duration GPScasts 60 3c-iii. Discovering A Router's Service Area 61 3c-iv. Hierarchical Router Structure and 62 Multicast Groups 63 3c-v. Routing Optimizations 64 3c-vi. Router-Failure Recovery Scheme 65 3c-vii. Domain Name Service Issues 66 4. Router Daemon and Host Library 67 4a. GPS Address Library - SendToGPS() 68 4b. Establishing A Default GPS Router 69 4c. GPSRouteD 70 4c-i. Configuration 71 4d. Multicast Address Resolution Protocol (MARP) 72 4e. Internet GPS Management Protocol (IGPSMP) 73 5. Working Without GPS Information 74 5a. Users Without GPS Modules 75 5b. Buildings block GPS radio frequencies. 76 What then? 77 6. Application Layer Solution 78 7. Reliability 79 8. Security Considerations 80 9. References 81 10. Author's Address 83 1. Introduction 85 In the near future GPS will be widely used allowing a broad variety 86 of location dependent services such as direction giving, navigation, 87 etc. In this document we propose a family of protocols and addressing 88 methods to integrate GPS into the Internet Protocol to enable the 89 creation of location dependent services such as: 91 o Multicasting selectively only to specific geographical 92 regions defined by latitude and longitude. For example, 93 sending an emergency message to everyone who is currently 94 in a specific area, such as a building or train station. 96 o Providing a given service only to clients who are within a 97 certain geographic range from the server (which may be mobile 98 itself), say within 2 miles. 100 o Advertising a given service in a range restricted way, say, 101 within 2 miles from the server, 103 o Providing contiguous information services for mobile users 104 when information depends on the user's location. In 105 particular providing location dependent book-marks, which 106 provides the user with any important information which 107 happens to be local (within a certain range) possibly 108 including other mobile servers. 110 The solutions which we present are flexible (scalable) in terms of 111 the target accuracy of the GPS. We also discuss cases when GPS cannot 112 be used (like inside buildings). 114 The main challenge is to integrate the concept of physical location 115 into the current design of the Internet which relies on logical 116 addressing. We see the following general families of solutions: 118 a) Unicast IP routing extended to deal with GPS addresses 120 b) GPS-Multicast solution 122 c) Application Layer Solution using extended DNS 124 The first two solutions are presented in this draft. We only sketch 125 the third solution. 127 1b. General Architecture 129 We will assume a general cellular architecture with base stations 130 called Mobile Support Stations (MSS). We will consider a wide variety 131 of cells, including outdoor and indoor cells. We will discuss both 132 cases when the mobile client has a GPS card on his machine and cases 133 when the GPS card does not work (i.e. - inside buildings). 135 We will assume that each MSS covers a cell with a well defined range 136 specified as a polygon of spatial coordinates and that the MSS is 137 aware of its own range. 139 1c. Scenarios of Usage and Interface Issues 141 Below, we list some possible scenarios of usage for the geographic 142 messaging. 144 Consider an example situation, of an area of land near a river. 145 During a severe rain storm, the local authorities may wish to send a 146 flood warning to all people living within a hundred meters of the 147 river. 149 For the interface to such messaging system we propose to use a zoom- 150 able map similar to the U.S. Census Bureau's Tiger Map Service. This 151 map would allow a user to view a geographical area at varying degrees 152 of magnitude. He could then use a pointing device, such as a mouse, 153 to draw a bounding polygon around the area which will receive the 154 message to be sent. The computer would then translate the drawn 155 polygon into GPS coordinates and use those coordinates when sending 156 and routing the message. Geographical regions specified using this 157 zoom-able map could be stored and recalled at a later time. This 158 zoom-able map is analogous to the IP address books found in many 159 email programs. 161 To continue with the above example, local officials would call up a 162 map containing the river in danger of overflowing. They would then 163 hand-draw a bounding polygon around all of the areas at least a 164 hundred yards from the river. They would specify this to be the 165 destination for a flood warning email to all residents in the area. 166 The warning email would then be sent. Similar applications include 167 traffic management (for example, reaching vehicles which are stuck in 168 traffic) and security enforcement. 170 Other applications involve general client server applications where 171 servers are selected on the basis of the geographic distance. For 172 example, one may be interested in finding out all car dealers within 173 2 miles from his/her location. This leads to an extension of the Web 174 concept in which location and distance play important roles in 175 selecting information. We are currently in the process of 176 implementing location dependent book-marks (hot lists) in which pages 177 associated with static and mobile servers which are present within a 178 certain distance from the client are displayed on the client's 179 terminal. 181 2. Addressing Model 183 Two-dimensional GPS positioning offers latitude and longitude 184 information as a four dimensional vector: 186 188 where Direction is one of the four basic values: N, S, W, E; hours 189 ranges from 0 to 180 (for latitude) and 0 to 90 for longitude, and, 190 finally, minutes and seconds range from 0 to 60. 192 Thus is an example of longitude and 193 is an example of latitude. 195 Four bytes of addressing space (one byte for each of the four 196 dimensions) are necessary to store latitude and four bytes are also 197 sufficient to store longitude. Thus eight bytes total are necessary 198 to address the whole surface of earth with precision down to 0.1 199 mile! Notice that if we desired precision down to 0.001 mile (1.8 200 meters) then we would need just five bytes for each component, or ten 201 bytes together for the full address (as military versions provide). 203 The future version of IP (IP v6) will certainly have a sufficient 204 number of bits in its addressing space to provide an address for even 205 smaller GPS addressable units. In this proposal, however, we assume 206 the current version of IP (IP v4) and we make sure that we manage the 207 addressing space more economically than that. We will call the 208 smallest GPS addressable unit a GPS-square. 210 2a. Using GPS for Destination Addresses 212 A destination GPS address would be represented by one of the 213 following: 215 o Some closed polygon such as: 217 circle( center point, radius ) 219 polygon( point1, point2, point3, ... , pointn) 221 where each point would be expressed using GPS-square 222 addresses. This notation would send a message to anyone 223 within the specified geographical area defined by the closed 224 polygon. 226 o site-name as a geographic access path 228 This notation would simulate the postal mail service. In 229 this manner, a message can be sent to a specific site by 230 specifying its location in terms of real-world names 231 such as the name of a specific site, city, township, 232 county, state, etc. This format would make use of the 233 directory service detailed later. 235 For example, if we were to send a message to city hall in Fresno, 236 California, we could send it by specifying either a bounding polygon 237 or the mail address. If we specify a bounding polygon, then we could 238 specify the GPS limits of the city hall as a series of connected 239 lines that form a closed polygon surrounding it. Since we have a 240 list of connected lines, we just have to record the endpoints of the 241 lines. Therefore the address of the city hall in Fresno could look 242 like: 244 polygon([N 45 58 23, W 34 56 12], [N 23 45 56, W 12 23 34], ... ) 246 Alternatively, since city hall in Fresno is a well-defined 247 geographical area, it would be simpler to merely name the 248 destination. This would be done by specifying "postal-like" address 249 such as city_hall.Fresno.California.USA. 251 For "ad hoc" specified areas such as, say a quad between 5th and 6th 252 Avenue and 43 and 46 street in New York, the polygon addressing will 253 be used. 255 Unfortunately, we will not be able to assume that we have enough 256 addressing space available in the IP packet addressing space to 257 address all GPS squares. Instead we will propose a solution which is 258 flexible in terms of the smallest GPS addressable units which we call 259 atoms. In our solution, a smaller available addressing space (in the 260 IP packet) will translate into bigger atoms. Obviously, we can use 261 as precise addressing as we want to in the body of the geographic 262 messages - the space limitations apply only to the IP addressing 263 space. 265 By a geographic address we mean an IP address assigned to a 266 geographic area or point of interest. Our solution will be flexible 267 in terms of the geographic addressing space. 269 Below, we will use the following two terms: 271 o Atoms: for smallest geographic areas which have 272 geographic address. 274 Thus, atoms could be as small as GPS squares but could be 275 larger 277 o Partitions: These are larger, geographical areas, which will 278 also have a geographic address. A state, county, town etc. 279 may constitute a partition. A partition will contain a number 280 of atoms. 282 Here are some examples of possible atoms and partitions: 284 o A rectangle, defined by truncating either longitude or 285 latitude part of the GPS address by skipping one or more 286 least significant digits 288 o A circle, centered in a specific GPS address with a 289 prespecified radius. 291 o Irregular shapes such as administrative domains: states, 292 counties, townships, boroughs, cities etc 294 Partitions and Atoms (which are of course special atomic partitions) 295 will therefore have geographic addresses which will be used by 296 routers. Areas of smaller size than atoms, or of "irregular shape" 297 will not have corresponding geographic addresses and will have to 298 handled with the help of application layer. 300 3. Routing 302 Let us now describe the suggested routing schemes responsible for 303 delivering a message to any geographical destination. 305 We will distinguish between two legs of the connection from the 306 sender to the receiver: the first leg from the sender to the MSS 307 (base station) and the second leg from the MSS to the receiver 308 residing in its cell. Our two solutions will differ on the first leg 309 of the connection and use the same options for the second leg, which 310 we call "last mile". 312 3a. GPS-Multicast Routing Scheme 314 Here, we discuss the first leg of routing: from the sender to the 315 MSS. We start with the multicasting solution. 317 Each partition and atom is mapped to a multicast address. The exact 318 form of this mapping is discussed further in this subsection. We 319 first sketch the basic idea. 321 This solution provides flexible mix of the multicast and application 322 level filtering for the geographic addressing. The key idea here is 323 to approximate the addressing polygon of the smallest partition which 324 contains it and using the multicast address corresponding to that 325 partition as the IP address of that message. The original polygon is 326 a part of the packet's body and the exact matching is done on the 327 application layer in the second leg of the route. 329 How is the multicast routing performed? 331 3a-i. Multicast Trees 333 The basic idea for the first level of routing using multicast is to 334 have each base station join multicast groups for all partitions which 335 intersect its range. Thus, MSS is not only aware of its own range 336 but also has a complete information about system defined partitions 337 which its range intersects. This information can be obtained upon MSS 338 installation, from the geographic database stored as a part of DNS. 340 If the proper multicast trees are constructed (using for example link 341 state multicast protocol) than the sender can simply determine the 342 multicast address of the partition which covers the original polygon 343 he wants to send his message to, use this multicast address as the 344 address on the packet and put the original polygon specification into 345 the packet content. In this way, multicast will assure that the 346 packet will be delivered to the proper MSS. 348 Example 350 For instance the MSS in New Brunswick may have its range intersect 351 the following atoms and partitions: Busch, College Avenue, Douglass 352 and Livingston Campuses of Rutgers University (atoms), New Brunswick 353 downtown area (atom), the Middlesex county partition and the NJ state 354 partition. Each of these atoms and partitions will be mapped into a 355 multicast address and the New Brunswick's MSS will have to join all 356 such multicast groups. 358 The message will be then specified and sent as follows: 360 The user will obtain the map of the New Brunswick area possibly from 361 the DNS extended properly with relevant maps. He will specify the 362 intended destination by drawing a polygon on the map which will be 363 translated into the sequence of coordinates. In the same time the 364 polygon will be "approximated" by the smallest partition which 365 contains that polygon. The multicast address corresponding to that 366 partition will be the IP address for packets carrying our message. 367 The exact destination polygon will be a part of each packet's body. 368 In this way the packet will be delivered using multicast routing to 369 the set of MSS which are members of the specified multicast group 370 (that is all MSS whose ranges intersect the given partition). Each 371 such MSS now will follow the "last mile" routing which is described 372 in detail, further in the proposal. Briefly speaking, the MSS could 373 then multicast the message further on the same multicast address and 374 the client will perform the final filtering o application layer, 375 matching its location (obtained from GPS) with the polygon specified 376 in the packet's body. Other solutions based entirely on multicasting 377 are also possible as described below. 379 End_Example 381 However, things cannot be as simple as described. For such a large 382 potential number of multicast groups if we build entire multicast 383 trees, the routing tables could be too large. Fortunately it is not 384 necessary to build complete multicast trees. Indeed, it in not 385 important to know precise location of each atom in California, from a 386 remote location, say in NJ. 388 Thus, we modify our simple solution by implementing the following 389 intuition: 391 The smaller is the size of the partition (atom) the more locally is 392 the information about that partition (atom) propagated. 394 Thus, only multicast group membership for very large partitions will 395 be propagated across the whole country. 397 For example, a base station in Menlo Park, California can intersect 398 several atoms ) and several larger which cover Menlo Park, such say 399 a partition which covers the entire San Mateo county, next which 400 cover the entire California and finally next which may cover the 401 entire west coast. This base station will have to join multicast 402 groups which correspond to all these rectangles. However, only the 403 information about multicast group corresponding to the West Coast 404 partition will be propagated to the East Coast routers. 406 However, a simple address aggregation scheme in which only a "more 407 significant portion" of address propagates far away would not work. 408 Indeed, in this case a remote router, say in NJ, could have several 409 aggregate links leading to California - in fact, in the worst case, 410 all its links could point to California since it could have received 411 a routing information to some location in California on any of those 412 links. 414 To avoid this, for each partition we distinguish one or a few MSS 415 which act as designated router(s) for that partition. For example, 416 the California partition, may have only three designated routers, one 417 in Eureka, another in Sacramento and yet another in LA. Only the 418 routing entries from the designated routers would be aggregated into 419 the aggregate address for California. Information coming from other 420 city routers will simply be dropped and not aggregated at all. This, 421 in addition to a standard selection of the shortest routes, would 422 restrict the number of links which lead to an aggregate address. In 423 particular, when there is only one designated router per partition, 424 there would only be one aggregate link in any router. This could lead 425 to non-optimal routing but will solve the problem of redundant links. 427 Even with a designated routers, it may happen that the same packet 428 will arrive at a given base station more than once due to different 429 alternative routes. Thus, a proper mechanism for discarding redundant 430 copies of the same packet should still be in place. In fact, due to 431 the possible intersections between ranges of the base stations the 432 possibility of receiving redundant copies of the same packets always 433 exist and has to be dealt with as a part of any solution. 435 3a-iii. Determining the geographic Multicast Addressing 437 Here we describe more specifically, the proposed addressing scheme 438 and the corresponding routing. 440 The addressing will be hierarchical. We will use the following 441 convention - each multicast address corresponding to a partitions or 442 an atoms will have the following format: 444 1111.GPS.S.C.x 446 where GPS is the specific code corresponding to the geographic 447 addressing subspace of the overall multicast addressing space. The S, 448 C and x parts are described below: 450 S - Encoding of the state. 451 Each state partition will have the address S/0/0. 453 C - County within a state. 454 Each county partition having the address S/C/0. 456 x - Atom within a county. 458 where 0's refer to the sequences of 0 bits on positions corresponding 459 to the "C part" and "x part" of address. 461 For example if GPS part is 6 bit,s which gives 1/64 of existing 462 multicast addresses to the geographic addressing we have 22 bits 463 left. The S part will take first 6 bits, C part next 6 bits (say) 464 and then the next 10 bits encode different atoms (within a county). 465 Thus, in our terminology the proposed addressing scheme has two types 466 of partitions: states and counties. 468 We will assume that the GPS network will consist of all base stations 469 (MSS) in addition the rest of the fixed network infrastructure. The 470 designated GPS routers however, will only be selected from the 471 population of MSS. Specifically, there will be state dedicated and 472 county dedicated routers. 474 The concept of the designation will be implemented as follows. From 475 the set of all MSS, only certain MSS will play a role of designated 476 routers for county and state partitions. Non-designated MSS will 477 only join multicast groups which correspond to the GPS atoms but not 478 GPS partitions that they intersect. The MSS which is a designated 479 router for a county partition will join the multicast group of the 480 county in which it is located, but not the state. Finally the state 481 designated router will also join the multicast address corresponding 482 to the state it is located in. 484 3a-iv. Building Multicast Trees 486 We assume that each router has geographic information attached to it 487 - in the same format as we use for multicast mapping, S/C/x - it 488 encodes the atom that contains the router. 490 The multicast tree is built by a router propagating its multicast 491 memberships to the neighboring routers. A given router will only 492 retain certain addresses though, to follow the intuition of not 493 retaining a specific information which is far away. 495 This is done as follows: the router (not necessarily the MSS based 496 router) with the address S/C/x will only retain addresses about 497 S'/0/0, S/C'/0 for S' and C' different from S and C and S/C/x for all 498 x. Thus, it will drop all the addresses of the form S'/C'/y for all 499 S' different that S except those with C'=0 and y=0, as well as all 500 the addresses of the form S/C'/y with C' different from C except 501 those with y=0. Hence, these addresses will not be forwarded any 502 further either. 504 Thus, notice that only the information coming from designated routers 505 will be forwarded further away, since the non-designated routers are 506 not allowed to join the multicast groups which correspond to the 507 states and counties. Consequently, their multicast membership 508 information will be not be propagated. 510 In this way a router at S/C/x will not bother about specific 511 locations within S'/C'/y since they are "too far". 513 Notice that this service may not be provided everywhere so we may not 514 have to use all multicast addresses even within those assigned for 515 geographic addresses. 517 Notice also that all of this is flexible - if we have more multicast 518 addresses available (IP v 6) we will get more precise addressing due 519 to smaller atoms. 521 3a-v. GPS Routing 523 Given a packet we always look for the "closest" match in the routing 524 table. If there is a complete match we follow such a link, if not we 525 follow the address with the x-part 0'd in (county address) if there 526 is none with the county which agrees with the destination county than 527 we look at the entry which agrees with the state part of the 528 destination address. 530 3a-vi. DNS Issues 532 How does the client find out the multicast address on which the 533 packet is to be sent? We assume that the local name server has the 534 complete state/county hierarchy and that each county map can be 535 provided possibly with the "grid" of atoms and partitions already 536 clearly marked. 538 Points of interests within a county can be attached multicast address 539 just as atoms. Then a given base station would have to join multicast 540 groups of the points of interests that it covers. 542 The final stage is for the receiver to look at the polygon (point of 543 interest) which is encoded in the body of the multicast packet and 544 decide on the basis of its own GPS location if this packet is to be 545 received or not. Doing it on the application layer simplifies many 546 routing issues. There is a tradeoff, however, specially when we have 547 very short S/C/x addresses and base stations which do not cover the 548 given polygon in fact are reached unnecessarily. This may happen and 549 it needs to be determined what is the number of the multicast 550 addresses which are necessary to reduce this "false" alarms to the 551 minimum. 553 3a-viii. Estimations 555 Assume average cell size of, say, 2km x 2km and the average state 556 size: say 200,000 square km, the average county size: say 4,000 557 square km. 559 A reasonable size of the atom is around the size of the cell since 560 then we do not hit wrong cells too often. 562 Therefore we need the x addressing part of the S/C/x to encode 563 4,000/4 cells: 1.000 atoms. Thus we need 10 bits for x 564 part. With 6 bits for the state and 6 bits for the county that gives 565 22 bits which is 1/64 of the total IP v4 multicast addressing space. 567 With IPv6 we will have, of course, much more addressing space which 568 we can use for the GPS multicast routing. 570 3b. "Last Mile" Routing 571 Multicasting will be used for the last mile routing in both our 572 solutions (i.e the one just discussed and the geometric routing 573 solution described next), but in different ways. 575 3b-i. Application Level Filtering 577 The MSS will forward the geographic message on its wireless link 578 under a multicast address. This multicast address will either be the 579 same for all locations in the range of the MSS's cell or, there will 580 be several addresses corresponding to atoms which intersect the given 581 cell. Additionally, a complete GPS address (for example in the form 582 of the polygon) will be provided in the body of the packet and the 583 exact address matching will be performed on the application layer. 584 The receiver, knowing its GPS position uses it to match against the 585 polygon address. The GPS position can be obtained by the receiver 586 either from the GPS card or, indoors, from the indoor base station 587 which itself knows its GPS position as a part of configuration file. 589 3b-ii. Multicast Filtering 591 In multicast level filtering, the base station assigns a temporary 592 multicast address to the addressing polygon in a message. It will 593 send out a directive on the cell's specially assigned multicast 594 address. All mobile clients who reside in that cell are members of 595 that special multicast group (one per MSS). The directive sent by the 596 MSS will contain the pair consisting of the temporary multicast 597 address together with the polygon. To improve the reliability this 598 message will be multicast several times. The clients, knowing their 599 GPS positions will than join the temporary multicast groups if their 600 current locations are within the advertised polygon. The MSS will 601 then send out the real message using the temporary multicast address. 603 The temporary multicast address would be cached for a period of time. 604 If more packets for the same polygon arrive in a short period of 605 time, they will be sent out on the same multicast address. If not, 606 then the multicast address is dropped and purged from the cache. 607 Filtering on the client's station is then performed entirely on the 608 IP level. This solution introduces additional delay (needed to join 609 the temporary multicast group) but reduces the number of irrelevant 610 packets received by the client. This especially important for very 611 long messages. 613 3b-iii. Computers on Fixed Networks 615 Fixed-network computers should also monitor all of the mandatory 616 multicast addresses for their site and GPS square. In this manner, 617 the fixed computers will also receive messages sent to specific GPS- 618 addresses. 620 Modified base stations would still be in charge of multicasting the 621 messages to the computers. These base stations would have the same 622 GPS-routing functionality as the mobile computer base stations. 623 Their main difference would be that the mobile computer base stations 624 would use radio frequencies to multicast their messages and the fixed 625 network base stations use the local Ethernet or Token Ring network. 627 The next scheme differs from the GPS multicast scheme described above 628 only on the first leg of the route, from the sender to the MSS. The 629 "last mile" from the MSS to the final destination will have the same 630 options as described above. 632 3c. Geometric Routing Scheme (GEO) 634 The Geometric Routing Scheme (GEO) uses the polygonal geographic 635 destination information in the GPScast header directly for routing. 636 GEO routing is going to be implemented in the Internet Protocol (IP) 637 Network layer in a manner similar to the way multicast routing was 638 first implemented. That is, a virtual network which uses GPS 639 addresses for routing will be overlayed onto the current IP 640 internetwork. We would accomplish this by creating our own GPS- 641 address routers. These routers would use tunnels to ship data 642 packets between them and between the routers and base stations. 644 3c-i. Routing Overview 646 Sending a GPScast message involves three steps: sending the message, 647 shuttling the message between routers, and receiving the message. 649 Sending a GPScast message is very similar to sending a UDP datagram. 650 The programmer would use the GPScast library routine SendToGPS(). 651 Among other parameters, this routine will accept the GPS polygonal 652 destination address and the body of the message. The SendToGPS() 653 routine will encapsulate the GPScast message in a UDP datagram and 654 send it to the class E address 240.0.0.0. Previously, the system 655 administrator will have specified in the /etc/rc.local or /etc/rc.ip 656 file a route command that will specify that packets with the address 657 240.0.0.0 will instead be sent to the address of the local GPS 658 router. This will have the effect of sending the datagram to the 659 nearest GPS router. 661 Before explaining how the GPS routers shuttle the GPScast message to 662 its destination, an introduction to routers and their different parts 663 is in order. For scalability purposes, GPS routers are arranged in a 664 hierarchical fashion. Each layer would correspond to a distinct 665 geographic area, such as a state or a city. At the top would be 666 country-wide routers in charge of moving messages from one end of the 667 country to another. At the bottom would be campus or department 668 routers in charge of moving messages between the base stations. See 669 Figure 1. 671 Country-Router(s) 672 / \ 673 State-Router(s) 674 / \ 675 City-Router(s) 676 / \ 677 Router Router 678 / | \ | \ 679 Base Base Base Base Base 681 Figure 1: Hierarchy of routers. 683 A GPS router essentially consists of three parts: a service area 684 table containing the geographic area serviced by the router and each 685 of its hierarchical children, a hashed cache of previous actions, and 686 a table containing the IP addresses of at least the router's children 687 and the router's parent. In the case of a bottom-layer campus 688 router, the service area table will contain polygons describing the 689 geographic reach of each child base station's cell. The polygon 690 created from the union of all of the router's child base stations' 691 polygons defines the service area of the router. 693 Once the datagram arrives at a GPS router, the router strips the 694 datagram off, thereby, leaving it with the original GPScast message. 695 First the router must determine if it services any part of the area 696 of the destination polygon. To do this, the router finds the 697 intersection between the destination polygon and the polygon 698 describing the router's service area. The polygon intersection 699 algorithm used is described by O'Rourke in his paper, A New Linear 700 Algorithm for Intersecting Convex Polygons. This algorithm requires 701 order N-squared time in the worst case. If the intersection result 702 is null, then the router simply sends the message to its parent 703 router. 705 ------ Destination Polygon 706 | A | 707 -------------- 708 | | B | | Router's Service Area Polygon 709 -------------- 710 | C | 711 ------ 713 Figure 2: Polygon Difference 715 However, if the result is not null, then the router does service the 716 area described by the intersection polygon. The router now subtracts 717 its service area from the destination polygon and sends the rest to 718 it's parent router. This subtraction step is actually a by-product 719 of the intersection algorithm. Using the example in Figure 2, the 720 destination polygon and the router's service area polygon intersect 721 at the region labeled B. Therefore, the router will subtract out the 722 B section and send the remaining sections A and C to its parent 723 router. 725 Continuing with the example, the router now uses the intersection 726 polygon B to to determine which base station (or stations) will 727 receive the GPScast message. The router finds the intersection 728 between the region B and the polygon of each base station's cell. 729 Those base station polygons which intersect the region B will be sent 730 the GPScast message. Processes on Mobile Hosts serviced by these 731 base stations will now use the routine RecvFromGPS() to receive the 732 GPScast message. 734 3c-ii. Supporting Long-Duration GPScasts 736 Most likely, there will be a need to support sending real-time 737 continuous media to a GPS destination. This continuous media could 738 be an audio GPScast or a video GPScast. This would require that 739 jitter be reduced in order to minimize disturbing artifacts in the 740 audio or video playback. Continually checking the destination 741 geometry of each packet would incur unnecessary delays and may 742 promote jitter. 744 Therefore, the router will keep a hashed cache of the latest GPScast 745 packets and their destinations. Each cache item will be hashed using 746 the Sender Identification included in the header of GPScast messages 747 as the key. Each cache item will contain a time stamp and a list of 748 the next hops for that GPScast. When the time stamp exceeds a 749 certain limit, then the cache item will be dropped. The list of next 750 hops is a list of the IP addresses of the base stations, peer 751 routers, and parent router which are to receive a copy of the GPScast 752 messages. 754 When a router receives a GPScast packet, it will use the incoming 755 packet's Sender Id as a key into the hashed cache. If this is not 756 the first packet to arrive for this destination and if the timer on 757 the hash table entry has not yet expired, then the hashed cache will 758 return a list of all of the destination addresses to which copies of 759 the packet must be sent. Copies of the packet are sent to all of 760 these destinations and the hash entry's time stamp is updated. 762 If no hash table entry is found (i.e.- this is the first packet 763 encountered for this destination address), then the normal geometry 764 checking routine would take over. A new cache entry is made 765 recording all of the next-hop destination addresses of the GPScast. 766 In this manner, if several other packets with the same GPS 767 destination follow this first packet, the router can use the hash 768 table to look-up the destination base stations instead of calculating 769 it using geometry. 771 3c-iii. Discovering A Router's Service Area 773 When the router is initiated, it will consult its configuration file. 774 One of the items it will find in the file will be the multicast 775 address of the base station group to which all of its child base 776 stations are members. The router will join this group and then send 777 out Service Area Query messages to this multicast group periodically 778 to discover and to refresh its knowledge of its children base 779 stations and the geographical areas serviced by them. 781 Queries are issued infrequently (no more than once every five 782 minutes) so as to keep the IGPSMP overhead on the network very low. 783 However, since the query is issued using unreliable multicast 784 datagrams, there is a chance that some base stations may not receive 785 the query. This is important in two cases: when a child node fails 786 and when a router first boots up. The case of a failed child node 787 will be explained later. However, when a router first boots up, it 788 can issue several queries in a small amount of time in order to 789 guarantee that base stations will receive the query and to, 790 therefore, build up its knowledge about its child base stations 791 quickly. 793 Base stations respond to a Service Area Query by issuing a Service 794 Area Report. This report is issued on the same multicast group 795 address that all of the base stations have joined. The report 796 contains the geographical service area of the base station. In order 797 to avoid a sudden congestion of reports being sent at the same time, 798 each base station will initiate a random delay timer. Only when the 799 timer expires will the base station send its report. 801 For every base station that responds, the router will create an IP 802 tunnel between it and the base station. This tunnel will carry the 803 GPScast packet traffic between the base station and the router. Each 804 responding base station and its geographic area of service will also 805 be included in the router's geometric routing table as a possible 806 destination for GPScast packets. Any base station that does not 807 respond for ten continuous Service Area Queries will be considered 808 unreachable and will be dropped from the routing table. 810 3c-iv. Hierarchical Router Structure and Multicast Groups 812 R5----------------------R6 813 / \ / \ 814 R1---------R2 R3---------R4 815 / | \ / | \ / | \ / | \ 816 b1 b2 b3 b4 b5 b6 b7 b8 b9 b10 b11 b12 818 Figure 3: Two peer routers (R5 and R6) cooperatively servicing four 819 child routers (R1 - R4). 821 For scalability purposes, a hierarchy of routers is used to transport 822 messages from a sender to a receiver. Each layer of peer routers 823 would have its own multicast group address for the exchange of 824 Service Area Queries and Reports between the peer routers. However, 825 routers in distinct subtrees need not know about the routers in other 826 subtrees. Therefore, multicast group addresses will also differ 827 between hierarchy subtrees. See figure 3. For instance, routers R1 828 and R2 would share a multicast group and would know about each other. 829 At the same time, routers R3 and R4 would share a different multicast 830 group and would know about each other. However, routers R1 and R2 831 would not know about R3 and R4, and vice versa. 833 But how will the router know the location and number of its peer 834 routers and who its parent router is? As mentioned before, the 835 router consults its configuration file upon start-up. Included in 836 this configuration file will be the the address of its parent router 837 and the multicast group address that the peer routers will use. This 838 peer multicast group address will be used in the same manner as the 839 base station multicast group address. It will be used to send and 840 receive Service Area Queries and Reports between the parent router 841 and the peer routers. There is only one difference. When a router 842 sends a Service Area Report, in addition to reporting its 843 geographical service area, a router will include the multicast 844 address of its children base stations. The reason for this is 845 explained in the router-failure recovery scheme described below. 847 3c-v. Routing Optimizations 849 The optimization described here attempts to reduce the latency of a 850 GPScast. It does so by reducing the the number of hops a packet must 851 traverse before finding its destination. The intuition behind the 852 idea is this: instead of going to the parent router and then to the 853 sibling, simply go to the sibling directly. As an additional 854 benefit, this method prevents the parent router from becoming a 855 bottleneck or a point of failure in the routing scheme. 857 In this optimization, when a router attempts to determine who will 858 receive the GPS packet, it considers its peer routers as if they were 859 also its children in the routing hierarchy. This means that the 860 router will consider its service area to be the union of the service 861 areas of its children and its peer routers. Also, when the 862 destination polygon intersects the router's service area polygon, the 863 router will forward a copy of the GPScast packet to any child or peer 864 router whose geographic service area contains or touches the packet's 865 GPS destination polygon. 867 However, before it sends a copy of the packet to a peer router, it 868 first finds the polygon: 870 P = D /\ S 872 where D stands for the packet's destination GPS polygon, S is the 873 polygon representing the service area of the peer router, and P is 874 the polygon that represents the intersection of D and S. The polygon 875 P is substituted for the destination polygon D in the packet and only 876 then is the packet forwarded to the peer router. This is necessary 877 because the peer router will be using that same routing algorithm. 878 Therefore, if the peer router receives a packet with the original 879 destination polygon D, it will also route copies of the packet to all 880 of its qualifying peer routers causing a chain of packet copies being 881 bounced back and forth. 883 3c-vi. Router-Failure Recovery Scheme 884 In the case of a router failure, the system should be able to route 885 around the failed router and continue to service GPScast messages. 886 The responsibility of detecting whether a router has failed or not 887 falls to the parent router. Using Figure 3 as an example router 888 hierarchy, the parent router R5 periodically sends out Service Area 889 Query IGPSMP messages on its children's multicast group address. 890 Thus, the child routers R1 and R2 will both receive this query. 891 Normally, both routers will respond with a Service Area Report 892 message. This message contains a polygon describing their service 893 areas and the multicast group address of their children. 895 However, if a router, R1, does not respond to ten continuous queries, 896 then it must be considered to have failed. Upon detecting this, the 897 parent router R5 will send a Set Service Area message to the child 898 router, R2 telling it to assume responsibility for the base stations 899 underneath the failed R1 router. In this Set Service Area message, 900 the parent router includes the multicast group address of R1's 901 children. The R2 router uses this multicast address to learn the 902 service areas and IP addresses of R1's children. The R2 router then 903 issues a Service Area Report advertising its new enlarged service 904 area responsibilities. All peer and parent routers will then update 905 their routing tables to include this new information. When the 906 failed router, R1, restarts, it will declare that it is alive and 907 that it is again servicing its area. All routers will then again 908 update their routing tables. 910 In the case that there is no parent router, such as at the top of the 911 routing hierarchy, then each peer router will keep track of its 912 neighbors. If a neighbor router fails, then the first neighbor 913 router to declare that it is taking over the base stations for the 914 failed router will take responsibility. The rest continues as 915 before. 917 3c-vii. Domain Name Service Issues 919 Domain Name Servers (DNS) could be used to facilitate the use of GPS 920 geographic addressing for sites of interest. The aim is to describe 921 specific geographic sites in a more natural and real-world manner 922 using a postal-service like addressing method. Essentially, the DNS 923 would resolve a postal-service like address, such as 924 City_Hall.New_York_City.New_York, into the IP address of the GPS 925 router responsible for that site. The GPS router would then route 926 the message to all available recipients in the site. 928 The DNS would be used when a message is sent using the 929 site-code.city-code.state-code.country-code 931 addressing scheme. The DNS would evaluate the address in reverse 932 starting with the country code, then the state code, etc. This is 933 the same method used currently by the IP DNS service to return IP 934 addresses based on the country or geographic domains. 936 4. Router Daemon and Host Library 938 4a. GPS Address Library - SendToGPS() 940 A library for GPS address routing will be constructed. The main 941 routines contained in this library will be the SendToGPS() and 942 RecvFromGPS() commands. SendToGPS() has the following syntax: 944 SendToGPS(int socket, GPS-Address *address, char *message, int size) 946 where socket is a previously created datagram socket, address is a 947 filled GPS-Address structure with the following form: 949 typedef _GPS-Address { 950 enum { point, circle, polygon } type; 951 char *mail-address; 952 struct 953 { 954 enum { North, South, West, East } dir; 955 int hours, minutes, seconds; 956 } *points; 958 } GPS-Address; 960 and message and size specify the actual message and its size. The 961 SendToGPS() routine will take the GPS-addressed message, encapsulate 962 it in an IP packet, and then send it as a normal IP datagram. The 963 message is encapsulated in the following manner: 965 -------------------------------------------------------- 966 | IP Header with destination address set to 240.0.0.0 | 967 -------------------------------------------------------- 968 | Sender Identifier | 969 -------------------------------------------------------- 970 | Address Type - Circle|Polygon | 971 -------------------------------------------------------- 972 | Actual GPS Address (see below) | 973 -------------------------------------------------------- 974 | Body of Message | 975 -------------------------------------------------------- 977 where the Sender Identifier would consist of a combination of the 978 sender's process id, host IP address, and the center of the 979 destination polygon. The Actual Address would be one of the 980 following: 982 circle - single GPS address and range measured in centiminutes. 984 polygon - list of GPS addresses terminated by the impossible 985 address: N 255 255 255. 987 RecvFromGPS() has the following syntax: 989 RecvFromGPS(int socket,GPS-Address *address,char *message,int size) 991 where socket is a previously created datagram socket, address is an 992 empty GPS-Address structure, and message and size specify message 993 buffer and its size. 995 4b. Establishing A Default GPS Router 997 The default GPS router is determined using the unicast routing table 998 found in the UNIX kernel. The local system administrator will have 999 previously adjusted the table so that all GPScast messages are sent 1000 to the local GPS router. However, if there is no route for GPScast 1001 messages in the table, then all messages will, by default, be sent to 1002 the default gateway. If the default gateway does not support GPScast 1003 messages, then all attempts to send a GPScast will return an error. 1005 By default, all GPScast messages will initially have as their 1006 destination the class E address 240.0.0.0. A route will be added to 1007 the kernel routing table by the system administrator for this 1008 address. The route will specify the location of the local GPS 1009 router. The "route" command will be used to affect the routing table 1010 and it can be placed in the /etc/rc.local or /etc/rc.ip files so that 1011 it will take effect each time the computer is booted. For example, 1012 to specify that GPScast messages addressed to 240.0.0.0 should, by 1013 default, be sent to the router which resides on a computer on the 1014 same subnet with local address 128.6.5.53, use the following: 1016 /etc/route add host 240.0.0.0 128.6.5.53 0 1018 If the default destination for GPScast messages is a host that does 1019 not support GPS addressing, then Network Unreachable errors will be 1020 returned to any process attempting to route GPScasts through that 1021 host. 1023 4c. GPSRouteD 1025 In order to provide the capability of GPS address routing throughout 1026 an IPv4-based internetwork, special-purpose routers will be created 1027 to support GPS address routing on top of the current Internet. These 1028 routers, which will be called GPSRouteD, will use virtual point-to- 1029 point links called tunnels in order to connect two GPSRouteDs 1030 together over regular unicast networks. The tunnels work by 1031 encapsulating the GPS address messages in IP datagrams and then 1032 transmitting the message to the host on the other end of the tunnel. 1033 In this manner, the GPS address messages look like normal unicast 1034 packets to all IPv4 routers in between the two GPS address routers. 1035 At the end of the tunnel, the receiving GPSRouteD removes the GPS 1036 address message from the datagram and continues the routing process. 1038 By using tunnels, the GPS routers can be established as a virtual 1039 internetwork throughout the current Internet without regard for the 1040 physical properties of the underlying networks. Moreover, the use of 1041 tunnels means that the host on which the router daemon is running 1042 need not be connected to more than one subnet in order for the router 1043 to forward GPS messages. This virtual internetwork would be 1044 responsible for routing GPS address messages only. This virtual 1045 network, however, is not intended to be a permanent solution and is 1046 only intended to provide a means of supporting GPS address routing 1047 until it gains wider acceptance and support in the Internet 1048 infrastructure. 1050 4c-i. Configuration 1052 When a GPSRouteD initially executes, it first checks the file 1053 /etc/GPSRouteD.conf for configuration commands to add tunnel and 1054 multicast links to other GPS address routers. There are two kinds of 1055 configuration commands: 1057 multicast 1059 tunnel 1060 1062 The tunnel command is used to create a tunnel between the local host 1063 on which the GPSRouteD executes and a remote host on which another 1064 GPSRouteD executes. The tunnel must be set up in the GPSRouteD.conf 1065 files at both ends before it will be used. 1067 The multicast command tells the router which multicast addresses to 1068 join. These addresses will carry IGPSMP messages and replies. The 1069 router will use these IGPSMP messages to build up and keep current 1070 its own internal routing table. 1072 4d. Multicast Address Resolution Protocol (MARP) 1074 Of course, this begs the question, how will the individual computers 1075 know which multicast addresses to join? For example, an MH would 1076 have to join the multicast address of its current cell so that it can 1077 receive GPScast messages (using application-level filtering) or 1078 directions to join other multicast groups (using multicast 1079 filtering). We have designed a protocol called Multicast Address 1080 Resolution Protocol (MARP) that works the same way as Reverse Address 1081 Resolution Protocol (RARP). However, instead of returning the IP 1082 address of the MH, it will return multicast group address of the cell 1083 the MH is currently in. The MH would then join this multicast group. 1085 4e. Internet GPS Management Protocol (IGPSMP) 1087 The Internet GPS Management Protocol (IGPSMP) is used by GPS routers 1088 to report, query, and inform their router counterparts about their 1089 geographical service areas. The IGPSMP will also be used to verify 1090 that routers are correctly functioning. 1092 The vocabulary of IGPSMP will consist of six words: 1094 o set service area - Used by the parent router to set the 1095 geographic service area of a router. This is needed in 1096 order to automatically respond to router failure or new 1097 router boot-up. 1099 o confirm service area - confirms that a router has received 1100 its service area. 1102 o geographical service area query - This message will be used 1103 by a router to build up its geographical routing table. 1104 It is sent to all routers on the same level. 1106 o service area report - This message is sent in response to a 1107 query request. It contains a bounding closed polygon 1108 described using GPS coordinates which contains the service 1109 area for the router. 1111 o ping - This message is sent periodically to ascertain whether 1112 the router is currently functioning properly. Usually sent 1113 by the parent router in the hierarchy tree. 1115 o alive signal - Usually sent as a reply to the ping message. 1116 Used by a router to indicate that it is functioning 1117 correctly. It is also sent immediately after a router 1118 boots. 1120 All of IGPSMP messages will be sent on an all-routers multicast 1121 address for a particular hierarchy level. The exact multicast 1122 address can be set in the router configuration file. 1124 Note that for the GPS-Multicast routing scheme, the time-to-live 1125 value of the service area reports will be varied in order to control 1126 the distribution of the information. In GPS-Multicast routing, only 1127 the multicast group membership for very large partitions will be 1128 distributed throughout the country. Smaller partition may only be 1129 distributed to neighbor routers. 1131 5. Working Without GPS Information 1133 5a. Users Without GPS Modules 1135 Mobile users without GPS modules can still participate - though at a 1136 very reduced level. When an MH enters a cell, it can use an MARP to 1137 discover the local multicast group for that cell or atom. As the 1138 user roams from cell to cell, the mobile host can keep track of the 1139 current cell that the user is in and adds or drops the multicast 1140 groups pertaining to those cells. The user's GPS address can be set 1141 to be the center of the current cell. 1143 5b. Buildings block GPS radio frequencies. What then? 1145 Each room can have a radio beacon placed on the ceiling. The beacon 1146 will be weak enough so that it will not penetrate walls. Each radio 1147 beacon will have its own GPS-address associated with it which it will 1148 broadcast. When a mobile user enters a room, his MH will detect the 1149 beacon and read the beacon's GPS address. The GPS-address of the MH 1150 will be set to the GPS-address of the beacon. The MH will then use 1151 this beacon's GPS address in order to perform any message filtering 1152 that it needs to do. Now the mobile user can have a GPS-address 1153 associated with him even though he is indoors and his GPS-module is 1154 useless. 1156 6. Application Layer Solution 1158 In this subsection we sketch a third solution which relies more 1159 heavily on the DNS. 1161 In the application layer solution the geographic information is added 1162 to the DNS which provides the full directory information down to the 1163 level of the IP address of each base station and its area of coverage 1164 represented as a polygon of coordinates. 1166 A new first level domain - "geographic" is added to the set of first 1167 level domains. The second level domain names include states, the 1168 third, counties and finally, the fourth: polygons of coordinates, or 1169 so called points of interests. We can also allow, polygons to occur 1170 as elements of second, third domains to enable sending messages to 1171 larger areas. 1173 Thus a typical geographic address can look like 1175 city-hall-Palo-Alto.San-Mateo-County.California.geographic 1177 or 1179 Polygon.San-Mateo-County.California.geographic 1181 where Polygon is a sequence of coordinates. 1183 This geographic address is resolved in a similar way as the standard 1184 domain addresses are resolved today into a set of IP addresses of 1185 base stations which cover that geographic area. There are several 1186 possibilities here: 1188 a. A set of unicast messages is sent to all base stations 1189 corresponding to the IP addresses returned by the DNS. Each base 1190 station then forwards the message using either of the two last link 1191 solutions: application level or network level filtering. 1193 b. All the base stations join the temporary multicast group for the 1194 geographic area specified in the message. In this way we may avoid 1195 sending the same message across the same link several times. Thus, 1196 after the set of relevant base stations is determined by the DNS, the 1197 temporary multicast group is established and all packets with that 1198 multicast address are sent on that multicast address. 1200 c. Only one, central to the polygon base station is returned by the 1201 DNS just as in the IP unicast solution. However that "central" base 1202 station will have to forward messages to the other base stations 1203 within the polygon. 1205 Notice that we should distinguish between "small area" and "wide 1206 area" geographic mail. The "small area" mail will be most common and 1207 will most likely involve just one base station, favoring a simple 1208 form of solution (a). 1210 7. Reliability 1212 Should the geographic messages be acknowledged? 1214 Since we have no control if users are present in the target 1215 geographic area where the mail is distributed we do not see a need 1216 for individual acknowledgments from the message recipients. However, 1217 we believe that the base stations (MSS) covering the target area of 1218 geographic mail should acknowledge the messages. 1220 Typically only a few base stations will be involved since typically 1221 we will not cover very broad geographic areas anyway. We assume that 1222 the base stations, additionally to forwarding the the messages on 1223 their wireless interfaces will buffer them, either to periodically 1224 multicast them (emergency response) or to provide them to users who 1225 just entered a cell and download the "emergency stack" of messages 1226 for that area as a part of the service hand-off protocol. 1228 8. Security Considerations 1230 Some method of determining who has permission to send messages to a 1231 large geographical area is needed. For instance, perhaps only the 1232 mayor of New York City has permission to send a message to all of New 1233 York City. 1235 9. References 1236 S. Deering. Host Extensions for IP Multicasting. RFC 1112, (August 1237 1989) 1239 S. Deering. Multicast Routing in a Datagram Internetwork. Ph.D. 1240 Thesis, Stanford University, (December 1991) 1242 J. O'Rourke, C.B. Chien, T. Olson, and D. Naddor, A new linear 1243 algorithm for intersecting convex polygons, Computer Graphics and 1244 Image Processing 19, 384-391 (1982). 1246 J. Ioannidis, D. Duchamp, and G. Q. Maquire. IP-Based Protocols for 1247 Mobile Internetworking. Proc. of ACM SIGCOMM Symposium on 1248 Communication, Architectures and Protocols, pages 235-245, 1249 (September, 1991) 1251 10. Author's Address 1253 Tomasz Imielinski and Julio C. Navas 1254 Computer Science Department 1255 Busch Campus 1256 Rutgers, The State University 1257 Piscataway, NJ 1258 08855 1260 Phone: 908-445-3551 1261 EMail: {imielins,navas}@cs.rutgers.edu 1263 Network Working Group T. Imielinski 1265 Category: Experimental Computer Science, Rutgers University 1266 March 8, 1996 1268 GPS-Based Addressing and Routing 1270 1272 Status of this Memo 1274 This document is an Internet Draft. Internet Drafts are working 1275 documents of the Internet Engineering Task Force (IETF), its Areas, 1276 and its Working Groups. Note that other groups may also distribute 1277 working documents as Internet Drafts. 1279 Internet Drafts are draft documents valid for a maximum of six 1280 months. Internet Drafts may be updated, replaced, or obsoleted by 1281 other documents at any time. It is not appropriate to use Internet 1282 Drafts as reference material or to cite them other than as a 1283 "working draft" or "work in progress." 1285 To learn the current status of any Internet-Draft, please check the 1286 "1id-abstracts.txt" listing contained in the internet-drafts Shadow 1287 Directories on: 1289 ftp.is.co.za (Africa) 1290 nic.nordu.net (Europe) 1291 ds.internic.net (US East Coast) 1292 ftp.isi.edu (US West Coast) 1293 munnari.oz.au (Pacific Rim) 1295 Table of Contents 1297 1. Introduction 1298 1b. General Architecture 1299 1c. Scenarios of Usage: Interface Issues 1300 2. Addressing Model 1301 2a. Using GPS for Destination Addresses 1302 3. Routing 1303 3a. GPS Multicast Routing Scheme (GPSM) 1304 3a-i. GPS Rectangles 1305 3a-ii. Multicast Trees 1306 3a-iii. Determining the GPS Multicast 1307 Addressing 1308 3a-iv. Building Multicast Trees 1309 3a-v. Routing 1310 3a-vi. DNS Issues 1311 3a-vii. Application Layer Filtering 1312 3a-viii. Estimations 1313 3b. "Last Mile" Routing 1314 3b-i. Application Level Filtering 1315 3b-ii. Multicast Filtering 1316 3b-iii. Computers on Fixed Networks 1317 3c. Geometric Routing Scheme (GEO) 1318 3c-i. Routing Overview 1319 3c-ii. Supporting Long-Duration GPScasts 1320 3c-iii. Discovering A Router's Service Area 1321 3c-iv. Hierarchical Router Structure and 1322 Multicast Groups 1323 3c-v. Routing Optimizations 1324 3c-vi. Router-Failure Recovery Scheme 1325 3c-vii. Domain Name Service Issues 1326 4. Router Daemon and Host Library 1327 4a. GPS Address Library - SendToGPS() 1328 4b. Establishing A Default GPS Router 1329 4c. GPSRouteD 1330 4c-i. Configuration 1331 4d. Multicast Address Resolution Protocol (MARP) 1332 4e. Internet GPS Management Protocol (IGPSMP) 1333 5. Working Without GPS Information 1334 5a. Users Without GPS Modules 1335 5b. Buildings block GPS radio frequencies. 1336 What then? 1337 6. Application Layer Solution 1338 7. Reliability 1339 8. Security Considerations 1340 9. References 1341 10. Author's Address 1343 1. Introduction 1345 In the near future GPS will be widely used allowing a broad variety 1346 of location dependent services such as direction giving, navigation, 1347 etc. In this document we propose a family of protocols and addressing 1348 methods to integrate GPS into the Internet Protocol to enable the 1349 creation of location dependent services such as: 1351 o Multicasting selectively only to specific geographical 1352 regions defined by latitude and longitude. For example, 1353 sending an emergency message to everyone who is currently 1354 in a specific area, such as a building or train station. 1356 o Providing a given service only to clients who are within a 1357 certain geographic range from the server (which may be mobile 1358 itself), say within 2 miles. 1360 o Advertising a given service in a range restricted way, say, 1361 within 2 miles from the server, 1363 o Providing contiguous information services for mobile users 1364 when information depends on the user's location. In 1365 particular providing location dependent book-marks, which 1366 provides the user with any important information which 1367 happens to be local (within a certain range) possibly 1368 including other mobile servers. 1370 The solutions which we present are flexible (scalable) in terms of 1371 the target accuracy of the GPS. We also discuss cases when GPS cannot 1372 be used (like inside buildings). 1374 The main challenge is to integrate the concept of physical location 1375 into the current design of the Internet which relies on logical 1376 addressing. We see the following general families of solutions: 1378 a) Unicast IP routing extended to deal with GPS addresses 1380 b) GPS-Multicast solution 1382 c) Application Layer Solution using extended DNS 1384 The first two solutions are presented in this draft. We only sketch 1385 the third solution. 1387 1b. General Architecture 1389 We will assume a general cellular architecture with base stations 1390 called Mobile Support Stations (MSS). We will consider a wide variety 1391 of cells, including outdoor and indoor cells. We will discuss both 1392 cases when the mobile client has a GPS card on his machine and cases 1393 when the GPS card does not work (i.e. - inside buildings). 1395 We will assume that each MSS covers a cell with a well defined range 1396 specified as a polygon of spatial coordinates and that the MSS is 1397 aware of its own range. 1399 1c. Scenarios of Usage and Interface Issues 1401 Below, we list some possible scenarios of usage for the geographic 1402 messaging. 1404 Consider an example situation, of an area of land near a river. 1405 During a severe rain storm, the local authorities may wish to send a 1406 flood warning to all people living within a hundred meters of the 1407 river. 1409 For the interface to such messaging system we propose to use a zoom- 1410 able map similar to the U.S. Census Bureau's Tiger Map Service. This 1411 map would allow a user to view a geographical area at varying degrees 1412 of magnitude. He could then use a pointing device, such as a mouse, 1413 to draw a bounding polygon around the area which will receive the 1414 message to be sent. The computer would then translate the drawn 1415 polygon into GPS coordinates and use those coordinates when sending 1416 and routing the message. Geographical regions specified using this 1417 zoom-able map could be stored and recalled at a later time. This 1418 zoom-able map is analogous to the IP address books found in many 1419 email programs. 1421 To continue with the above example, local officials would call up a 1422 map containing the river in danger of overflowing. They would then 1423 hand-draw a bounding polygon around all of the areas at least a 1424 hundred yards from the river. They would specify this to be the 1425 destination for a flood warning email to all residents in the area. 1426 The warning email would then be sent. Similar applications include 1427 traffic management (for example, reaching vehicles which are stuck in 1428 traffic) and security enforcement. 1430 Other applications involve general client server applications where 1431 servers are selected on the basis of the geographic distance. For 1432 example, one may be interested in finding out all car dealers within 1433 2 miles from his/her location. This leads to an extension of the Web 1434 concept in which location and distance play important roles in 1435 selecting information. We are currently in the process of 1436 implementing location dependent book-marks (hot lists) in which pages 1437 associated with static and mobile servers which are present within a 1438 certain distance from the client are displayed on the client's 1439 terminal. 1441 2. Addressing Model 1443 Two-dimensional GPS positioning offers latitude and longitude 1444 information as a four dimensional vector: 1446 1448 where Direction is one of the four basic values: N, S, W, E; hours 1449 ranges from 0 to 180 (for latitude) and 0 to 90 for longitude, and, 1450 finally, minutes and seconds range from 0 to 60. 1452 Thus is an example of longitude and 1453 is an example of latitude. 1455 Four bytes of addressing space (one byte for each of the four 1456 dimensions) are necessary to store latitude and four bytes are also 1457 sufficient to store longitude. Thus eight bytes total are necessary 1458 to address the whole surface of earth with precision down to 0.1 1459 mile! Notice that if we desired precision down to 0.001 mile (1.8 1460 meters) then we would need just five bytes for each component, or ten 1461 bytes together for the full address (as military versions provide). 1463 The future version of IP (IP v6) will certainly have a sufficient 1464 number of bits in its addressing space to provide an address for even 1465 smaller GPS addressable units. In this proposal, however, we assume 1466 the current version of IP (IP v4) and we make sure that we manage the 1467 addressing space more economically than that. We will call the 1468 smallest GPS addressable unit a GPS-square. 1470 2a. Using GPS for Destination Addresses 1472 A destination GPS address would be represented by one of the 1473 following: 1475 o Some closed polygon such as: 1477 circle( center point, radius ) 1479 polygon( point1, point2, point3, ... , pointn) 1481 where each point would be expressed using GPS-square 1482 addresses. This notation would send a message to anyone 1483 within the specified geographical area defined by the closed 1484 polygon. 1486 o site-name as a geographic access path 1488 This notation would simulate the postal mail service. In 1489 this manner, a message can be sent to a specific site by 1490 specifying its location in terms of real-world names 1491 such as the name of a specific site, city, township, 1492 county, state, etc. This format would make use of the 1493 directory service detailed later. 1495 For example, if we were to send a message to city hall in Fresno, 1496 California, we could send it by specifying either a bounding polygon 1497 or the mail address. If we specify a bounding polygon, then we could 1498 specify the GPS limits of the city hall as a series of connected 1499 lines that form a closed polygon surrounding it. Since we have a 1500 list of connected lines, we just have to record the endpoints of the 1501 lines. Therefore the address of the city hall in Fresno could look 1502 like: 1504 polygon([N 45 58 23, W 34 56 12], [N 23 45 56, W 12 23 34], ... ) 1506 Alternatively, since city hall in Fresno is a well-defined 1507 geographical area, it would be simpler to merely name the 1508 destination. This would be done by specifying "postal-like" address 1509 such as city_hall.Fresno.California.USA. 1511 For "ad hoc" specified areas such as, say a quad between 5th and 6th 1512 Avenue and 43 and 46 street in New York, the polygon addressing will 1513 be used. 1515 Unfortunately, we will not be able to assume that we have enough 1516 addressing space available in the IP packet addressing space to 1517 address all GPS squares. Instead we will propose a solution which is 1518 flexible in terms of the smallest GPS addressable units which we call 1519 atoms. In our solution, a smaller available addressing space (in the 1520 IP packet) will translate into bigger atoms. Obviously, we can use 1521 as precise addressing as we want to in the body of the geographic 1522 messages - the space limitations apply only to the IP addressing 1523 space. 1525 By a geographic address we mean an IP address assigned to a 1526 geographic area or point of interest. Our solution will be flexible 1527 in terms of the geographic addressing space. 1529 Below, we will use the following two terms: 1531 o Atoms: for smallest geographic areas which have 1532 geographic address. 1534 Thus, atoms could be as small as GPS squares but could be 1535 larger 1537 o Partitions: These are larger, geographical areas, which will 1538 also have a geographic address. A state, county, town etc. 1539 may constitute a partition. A partition will contain a number 1540 of atoms. 1542 Here are some examples of possible atoms and partitions: 1544 o A rectangle, defined by truncating either longitude or 1545 latitude part of the GPS address by skipping one or more 1546 least significant digits 1548 o A circle, centered in a specific GPS address with a 1549 prespecified radius. 1551 o Irregular shapes such as administrative domains: states, 1552 counties, townships, boroughs, cities etc 1554 Partitions and Atoms (which are of course special atomic partitions) 1555 will therefore have geographic addresses which will be used by 1556 routers. Areas of smaller size than atoms, or of "irregular shape" 1557 will not have corresponding geographic addresses and will have to 1558 handled with the help of application layer. 1560 3. Routing 1562 Let us now describe the suggested routing schemes responsible for 1563 delivering a message to any geographical destination. 1565 We will distinguish between two legs of the connection from the 1566 sender to the receiver: the first leg from the sender to the MSS 1567 (base station) and the second leg from the MSS to the receiver 1568 residing in its cell. Our two solutions will differ on the first leg 1569 of the connection and use the same options for the second leg, which 1570 we call "last mile". 1572 3a. GPS-Multicast Routing Scheme 1574 Here, we discuss the first leg of routing: from the sender to the 1575 MSS. We start with the multicasting solution. 1577 Each partition and atom is mapped to a multicast address. The exact 1578 form of this mapping is discussed further in this subsection. We 1579 first sketch the basic idea. 1581 This solution provides flexible mix of the multicast and application 1582 level filtering for the geographic addressing. The key idea here is 1583 to approximate the addressing polygon of the smallest partition which 1584 contains it and using the multicast address corresponding to that 1585 partition as the IP address of that message. The original polygon is 1586 a part of the packet's body and the exact matching is done on the 1587 application layer in the second leg of the route. 1589 How is the multicast routing performed? 1591 3a-i. Multicast Trees 1593 The basic idea for the first level of routing using multicast is to 1594 have each base station join multicast groups for all partitions which 1595 intersect its range. Thus, MSS is not only aware of its own range 1596 but also has a complete information about system defined partitions 1597 which its range intersects. This information can be obtained upon MSS 1598 installation, from the geographic database stored as a part of DNS. 1600 If the proper multicast trees are constructed (using for example link 1601 state multicast protocol) than the sender can simply determine the 1602 multicast address of the partition which covers the original polygon 1603 he wants to send his message to, use this multicast address as the 1604 address on the packet and put the original polygon specification into 1605 the packet content. In this way, multicast will assure that the 1606 packet will be delivered to the proper MSS. 1608 Example 1610 For instance the MSS in New Brunswick may have its range intersect 1611 the following atoms and partitions: Busch, College Avenue, Douglass 1612 and Livingston Campuses of Rutgers University (atoms), New Brunswick 1613 downtown area (atom), the Middlesex county partition and the NJ state 1614 partition. Each of these atoms and partitions will be mapped into a 1615 multicast address and the New Brunswick's MSS will have to join all 1616 such multicast groups. 1618 The message will be then specified and sent as follows: 1620 The user will obtain the map of the New Brunswick area possibly from 1621 the DNS extended properly with relevant maps. He will specify the 1622 intended destination by drawing a polygon on the map which will be 1623 translated into the sequence of coordinates. In the same time the 1624 polygon will be "approximated" by the smallest partition which 1625 contains that polygon. The multicast address corresponding to that 1626 partition will be the IP address for packets carrying our message. 1627 The exact destination polygon will be a part of each packet's body. 1628 In this way the packet will be delivered using multicast routing to 1629 the set of MSS which are members of the specified multicast group 1630 (that is all MSS whose ranges intersect the given partition). Each 1631 such MSS now will follow the "last mile" routing which is described 1632 in detail, further in the proposal. Briefly speaking, the MSS could 1633 then multicast the message further on the same multicast address and 1634 the client will perform the final filtering o application layer, 1635 matching its location (obtained from GPS) with the polygon specified 1636 in the packet's body. Other solutions based entirely on multicasting 1637 are also possible as described below. 1639 End_Example 1641 However, things cannot be as simple as described. For such a large 1642 potential number of multicast groups if we build entire multicast 1643 trees, the routing tables could be too large. Fortunately it is not 1644 necessary to build complete multicast trees. Indeed, it in not 1645 important to know precise location of each atom in California, from a 1646 remote location, say in NJ. 1648 Thus, we modify our simple solution by implementing the following 1649 intuition: 1651 The smaller is the size of the partition (atom) the more locally is 1652 the information about that partition (atom) propagated. 1654 Thus, only multicast group membership for very large partitions will 1655 be propagated across the whole country. 1657 For example, a base station in Menlo Park, California can intersect 1658 several atoms ) and several larger which cover Menlo Park, such say 1659 a partition which covers the entire San Mateo county, next which 1660 cover the entire California and finally next which may cover the 1661 entire west coast. This base station will have to join multicast 1662 groups which correspond to all these rectangles. However, only the 1663 information about multicast group corresponding to the West Coast 1664 partition will be propagated to the East Coast routers. 1666 However, a simple address aggregation scheme in which only a "more 1667 significant portion" of address propagates far away would not work. 1668 Indeed, in this case a remote router, say in NJ, could have several 1669 aggregate links leading to California - in fact, in the worst case, 1670 all its links could point to California since it could have received 1671 a routing information to some location in California on any of those 1672 links. 1674 To avoid this, for each partition we distinguish one or a few MSS 1675 which act as designated router(s) for that partition. For example, 1676 the California partition, may have only three designated routers, one 1677 in Eureka, another in Sacramento and yet another in LA. Only the 1678 routing entries from the designated routers would be aggregated into 1679 the aggregate address for California. Information coming from other 1680 city routers will simply be dropped and not aggregated at all. This, 1681 in addition to a standard selection of the shortest routes, would 1682 restrict the number of links which lead to an aggregate address. In 1683 particular, when there is only one designated router per partition, 1684 there would only be one aggregate link in any router. This could lead 1685 to non-optimal routing but will solve the problem of redundant links. 1687 Even with a designated routers, it may happen that the same packet 1688 will arrive at a given base station more than once due to different 1689 alternative routes. Thus, a proper mechanism for discarding redundant 1690 copies of the same packet should still be in place. In fact, due to 1691 the possible intersections between ranges of the base stations the 1692 possibility of receiving redundant copies of the same packets always 1693 exist and has to be dealt with as a part of any solution. 1695 3a-iii. Determining the geographic Multicast Addressing 1697 Here we describe more specifically, the proposed addressing scheme 1698 and the corresponding routing. 1700 The addressing will be hierarchical. We will use the following 1701 convention - each multicast address corresponding to a partitions or 1702 an atoms will have the following format: 1704 1111.GPS.S.C.x 1706 where GPS is the specific code corresponding to the geographic 1707 addressing subspace of the overall multicast addressing space. The S, 1708 C and x parts are described below: 1710 S - Encoding of the state. 1711 Each state partition will have the address S/0/0. 1713 C - County within a state. 1714 Each county partition having the address S/C/0. 1716 x - Atom within a county. 1718 where 0's refer to the sequences of 0 bits on positions corresponding 1719 to the "C part" and "x part" of address. 1721 For example if GPS part is 6 bit,s which gives 1/64 of existing 1722 multicast addresses to the geographic addressing we have 22 bits 1723 left. The S part will take first 6 bits, C part next 6 bits (say) 1724 and then the next 10 bits encode different atoms (within a county). 1725 Thus, in our terminology the proposed addressing scheme has two types 1726 of partitions: states and counties. 1728 We will assume that the GPS network will consist of all base stations 1729 (MSS) in addition the rest of the fixed network infrastructure. The 1730 designated GPS routers however, will only be selected from the 1731 population of MSS. Specifically, there will be state dedicated and 1732 county dedicated routers. 1734 The concept of the designation will be implemented as follows. From 1735 the set of all MSS, only certain MSS will play a role of designated 1736 routers for county and state partitions. Non-designated MSS will 1737 only join multicast groups which correspond to the GPS atoms but not 1738 GPS partitions that they intersect. The MSS which is a designated 1739 router for a county partition will join the multicast group of the 1740 county in which it is located, but not the state. Finally the state 1741 designated router will also join the multicast address corresponding 1742 to the state it is located in. 1744 3a-iv. Building Multicast Trees 1746 We assume that each router has geographic information attached to it 1747 - in the same format as we use for multicast mapping, S/C/x - it 1748 encodes the atom that contains the router. 1750 The multicast tree is built by a router propagating its multicast 1751 memberships to the neighboring routers. A given router will only 1752 retain certain addresses though, to follow the intuition of not 1753 retaining a specific information which is far away. 1755 This is done as follows: the router (not necessarily the MSS based 1756 router) with the address S/C/x will only retain addresses about 1757 S'/0/0, S/C'/0 for S' and C' different from S and C and S/C/x for all 1758 x. Thus, it will drop all the addresses of the form S'/C'/y for all 1759 S' different that S except those with C'=0 and y=0, as well as all 1760 the addresses of the form S/C'/y with C' different from C except 1761 those with y=0. Hence, these addresses will not be forwarded any 1762 further either. 1764 Thus, notice that only the information coming from designated routers 1765 will be forwarded further away, since the non-designated routers are 1766 not allowed to join the multicast groups which correspond to the 1767 states and counties. Consequently, their multicast membership 1768 information will be not be propagated. 1770 In this way a router at S/C/x will not bother about specific 1771 locations within S'/C'/y since they are "too far". 1773 Notice that this service may not be provided everywhere so we may not 1774 have to use all multicast addresses even within those assigned for 1775 geographic addresses. 1777 Notice also that all of this is flexible - if we have more multicast 1778 addresses available (IP v 6) we will get more precise addressing due 1779 to smaller atoms. 1781 3a-v. GPS Routing 1783 Given a packet we always look for the "closest" match in the routing 1784 table. If there is a complete match we follow such a link, if not we 1785 follow the address with the x-part 0'd in (county address) if there 1786 is none with the county which agrees with the destination county than 1787 we look at the entry which agrees with the state part of the 1788 destination address. 1790 3a-vi. DNS Issues 1792 How does the client find out the multicast address on which the 1793 packet is to be sent? We assume that the local name server has the 1794 complete state/county hierarchy and that each county map can be 1795 provided possibly with the "grid" of atoms and partitions already 1796 clearly marked. 1798 Points of interests within a county can be attached multicast address 1799 just as atoms. Then a given base station would have to join multicast 1800 groups of the points of interests that it covers. 1802 The final stage is for the receiver to look at the polygon (point of 1803 interest) which is encoded in the body of the multicast packet and 1804 decide on the basis of its own GPS location if this packet is to be 1805 received or not. Doing it on the application layer simplifies many 1806 routing issues. There is a tradeoff, however, specially when we have 1807 very short S/C/x addresses and base stations which do not cover the 1808 given polygon in fact are reached unnecessarily. This may happen and 1809 it needs to be determined what is the number of the multicast 1810 addresses which are necessary to reduce this "false" alarms to the 1811 minimum. 1813 3a-viii. Estimations 1815 Assume average cell size of, say, 2km x 2km and the average state 1816 size: say 200,000 square km, the average county size: say 4,000 1817 square km. 1819 A reasonable size of the atom is around the size of the cell since 1820 then we do not hit wrong cells too often. 1822 Therefore we need the x addressing part of the S/C/x to encode 1823 4,000/4 cells: 1.000 atoms. Thus we need 10 bits for x 1824 part. With 6 bits for the state and 6 bits for the county that gives 1825 22 bits which is 1/64 of the total IP v4 multicast addressing space. 1827 With IPv6 we will have, of course, much more addressing space which 1828 we can use for the GPS multicast routing. 1830 3b. "Last Mile" Routing 1831 Multicasting will be used for the last mile routing in both our 1832 solutions (i.e the one just discussed and the geometric routing 1833 solution described next), but in different ways. 1835 3b-i. Application Level Filtering 1837 The MSS will forward the geographic message on its wireless link 1838 under a multicast address. This multicast address will either be the 1839 same for all locations in the range of the MSS's cell or, there will 1840 be several addresses corresponding to atoms which intersect the given 1841 cell. Additionally, a complete GPS address (for example in the form 1842 of the polygon) will be provided in the body of the packet and the 1843 exact address matching will be performed on the application layer. 1844 The receiver, knowing its GPS position uses it to match against the 1845 polygon address. The GPS position can be obtained by the receiver 1846 either from the GPS card or, indoors, from the indoor base station 1847 which itself knows its GPS position as a part of configuration file. 1849 3b-ii. Multicast Filtering 1851 In multicast level filtering, the base station assigns a temporary 1852 multicast address to the addressing polygon in a message. It will 1853 send out a directive on the cell's specially assigned multicast 1854 address. All mobile clients who reside in that cell are members of 1855 that special multicast group (one per MSS). The directive sent by the 1856 MSS will contain the pair consisting of the temporary multicast 1857 address together with the polygon. To improve the reliability this 1858 message will be multicast several times. The clients, knowing their 1859 GPS positions will than join the temporary multicast groups if their 1860 current locations are within the advertised polygon. The MSS will 1861 then send out the real message using the temporary multicast address. 1863 The temporary multicast address would be cached for a period of time. 1864 If more packets for the same polygon arrive in a short period of 1865 time, they will be sent out on the same multicast address. If not, 1866 then the multicast address is dropped and purged from the cache. 1867 Filtering on the client's station is then performed entirely on the 1868 IP level. This solution introduces additional delay (needed to join 1869 the temporary multicast group) but reduces the number of irrelevant 1870 packets received by the client. This especially important for very 1871 long messages. 1873 3b-iii. Computers on Fixed Networks 1875 Fixed-network computers should also monitor all of the mandatory 1876 multicast addresses for their site and GPS square. In this manner, 1877 the fixed computers will also receive messages sent to specific GPS- 1878 addresses. 1880 Modified base stations would still be in charge of multicasting the 1881 messages to the computers. These base stations would have the same 1882 GPS-routing functionality as the mobile computer base stations. 1883 Their main difference would be that the mobile computer base stations 1884 would use radio frequencies to multicast their messages and the fixed 1885 network base stations use the local Ethernet or Token Ring network. 1887 The next scheme differs from the GPS multicast scheme described above 1888 only on the first leg of the route, from the sender to the MSS. The 1889 "last mile" from the MSS to the final destination will have the same 1890 options as described above. 1892 3c. Geometric Routing Scheme (GEO) 1894 The Geometric Routing Scheme (GEO) uses the polygonal geographic 1895 destination information in the GPScast header directly for routing. 1896 GEO routing is going to be implemented in the Internet Protocol (IP) 1897 Network layer in a manner similar to the way multicast routing was 1898 first implemented. That is, a virtual network which uses GPS 1899 addresses for routing will be overlayed onto the current IP 1900 internetwork. We would accomplish this by creating our own GPS- 1901 address routers. These routers would use tunnels to ship data 1902 packets between them and between the routers and base stations. 1904 3c-i. Routing Overview 1906 Sending a GPScast message involves three steps: sending the message, 1907 shuttling the message between routers, and receiving the message. 1909 Sending a GPScast message is very similar to sending a UDP datagram. 1910 The programmer would use the GPScast library routine SendToGPS(). 1911 Among other parameters, this routine will accept the GPS polygonal 1912 destination address and the body of the message. The SendToGPS() 1913 routine will encapsulate the GPScast message in a UDP datagram and 1914 send it to the class E address 240.0.0.0. Previously, the system 1915 administrator will have specified in the /etc/rc.local or /etc/rc.ip 1916 file a route command that will specify that packets with the address 1917 240.0.0.0 will instead be sent to the address of the local GPS 1918 router. This will have the effect of sending the datagram to the 1919 nearest GPS router. 1921 Before explaining how the GPS routers shuttle the GPScast message to 1922 its destination, an introduction to routers and their different parts 1923 is in order. For scalability purposes, GPS routers are arranged in a 1924 hierarchical fashion. Each layer would correspond to a distinct 1925 geographic area, such as a state or a city. At the top would be 1926 country-wide routers in charge of moving messages from one end of the 1927 country to another. At the bottom would be campus or department 1928 routers in charge of moving messages between the base stations. See 1929 Figure 1. 1931 Country-Router(s) 1932 / \ 1933 State-Router(s) 1934 / \ 1935 City-Router(s) 1936 / \ 1937 Router Router 1938 / | \ | \ 1939 Base Base Base Base Base 1941 Figure 1: Hierarchy of routers. 1943 A GPS router essentially consists of three parts: a service area 1944 table containing the geographic area serviced by the router and each 1945 of its hierarchical children, a hashed cache of previous actions, and 1946 a table containing the IP addresses of at least the router's children 1947 and the router's parent. In the case of a bottom-layer campus 1948 router, the service area table will contain polygons describing the 1949 geographic reach of each child base station's cell. The polygon 1950 created from the union of all of the router's child base stations' 1951 polygons defines the service area of the router. 1953 Once the datagram arrives at a GPS router, the router strips the 1954 datagram off, thereby, leaving it with the original GPScast message. 1955 First the router must determine if it services any part of the area 1956 of the destination polygon. To do this, the router finds the 1957 intersection between the destination polygon and the polygon 1958 describing the router's service area. The polygon intersection 1959 algorithm used is described by O'Rourke in his paper, A New Linear 1960 Algorithm for Intersecting Convex Polygons. This algorithm requires 1961 order N-squared time in the worst case. If the intersection result 1962 is null, then the router simply sends the message to its parent 1963 router. 1965 ------ Destination Polygon 1966 | A | 1967 -------------- 1968 | | B | | Router's Service Area Polygon 1969 -------------- 1970 | C | 1971 ------ 1973 Figure 2: Polygon Difference 1975 However, if the result is not null, then the router does service the 1976 area described by the intersection polygon. The router now subtracts 1977 its service area from the destination polygon and sends the rest to 1978 it's parent router. This subtraction step is actually a by-product 1979 of the intersection algorithm. Using the example in Figure 2, the 1980 destination polygon and the router's service area polygon intersect 1981 at the region labeled B. Therefore, the router will subtract out the 1982 B section and send the remaining sections A and C to its parent 1983 router. 1985 Continuing with the example, the router now uses the intersection 1986 polygon B to to determine which base station (or stations) will 1987 receive the GPScast message. The router finds the intersection 1988 between the region B and the polygon of each base station's cell. 1989 Those base station polygons which intersect the region B will be sent 1990 the GPScast message. Processes on Mobile Hosts serviced by these 1991 base stations will now use the routine RecvFromGPS() to receive the 1992 GPScast message. 1994 3c-ii. Supporting Long-Duration GPScasts 1996 Most likely, there will be a need to support sending real-time 1997 continuous media to a GPS destination. This continuous media could 1998 be an audio GPScast or a video GPScast. This would require that 1999 jitter be reduced in order to minimize disturbing artifacts in the 2000 audio or video playback. Continually checking the destination 2001 geometry of each packet would incur unnecessary delays and may 2002 promote jitter. 2004 Therefore, the router will keep a hashed cache of the latest GPScast 2005 packets and their destinations. Each cache item will be hashed using 2006 the Sender Identification included in the header of GPScast messages 2007 as the key. Each cache item will contain a time stamp and a list of 2008 the next hops for that GPScast. When the time stamp exceeds a 2009 certain limit, then the cache item will be dropped. The list of next 2010 hops is a list of the IP addresses of the base stations, peer 2011 routers, and parent router which are to receive a copy of the GPScast 2012 messages. 2014 When a router receives a GPScast packet, it will use the incoming 2015 packet's Sender Id as a key into the hashed cache. If this is not 2016 the first packet to arrive for this destination and if the timer on 2017 the hash table entry has not yet expired, then the hashed cache will 2018 return a list of all of the destination addresses to which copies of 2019 the packet must be sent. Copies of the packet are sent to all of 2020 these destinations and the hash entry's time stamp is updated. 2022 If no hash table entry is found (i.e.- this is the first packet 2023 encountered for this destination address), then the normal geometry 2024 checking routine would take over. A new cache entry is made 2025 recording all of the next-hop destination addresses of the GPScast. 2026 In this manner, if several other packets with the same GPS 2027 destination follow this first packet, the router can use the hash 2028 table to look-up the destination base stations instead of calculating 2029 it using geometry. 2031 3c-iii. Discovering A Router's Service Area 2033 When the router is initiated, it will consult its configuration file. 2034 One of the items it will find in the file will be the multicast 2035 address of the base station group to which all of its child base 2036 stations are members. The router will join this group and then send 2037 out Service Area Query messages to this multicast group periodically 2038 to discover and to refresh its knowledge of its children base 2039 stations and the geographical areas serviced by them. 2041 Queries are issued infrequently (no more than once every five 2042 minutes) so as to keep the IGPSMP overhead on the network very low. 2043 However, since the query is issued using unreliable multicast 2044 datagrams, there is a chance that some base stations may not receive 2045 the query. This is important in two cases: when a child node fails 2046 and when a router first boots up. The case of a failed child node 2047 will be explained later. However, when a router first boots up, it 2048 can issue several queries in a small amount of time in order to 2049 guarantee that base stations will receive the query and to, 2050 therefore, build up its knowledge about its child base stations 2051 quickly. 2053 Base stations respond to a Service Area Query by issuing a Service 2054 Area Report. This report is issued on the same multicast group 2055 address that all of the base stations have joined. The report 2056 contains the geographical service area of the base station. In order 2057 to avoid a sudden congestion of reports being sent at the same time, 2058 each base station will initiate a random delay timer. Only when the 2059 timer expires will the base station send its report. 2061 For every base station that responds, the router will create an IP 2062 tunnel between it and the base station. This tunnel will carry the 2063 GPScast packet traffic between the base station and the router. Each 2064 responding base station and its geographic area of service will also 2065 be included in the router's geometric routing table as a possible 2066 destination for GPScast packets. Any base station that does not 2067 respond for ten continuous Service Area Queries will be considered 2068 unreachable and will be dropped from the routing table. 2070 3c-iv. Hierarchical Router Structure and Multicast Groups 2072 R5----------------------R6 2073 / \ / \ 2074 R1---------R2 R3---------R4 2075 / | \ / | \ / | \ / | \ 2076 b1 b2 b3 b4 b5 b6 b7 b8 b9 b10 b11 b12 2078 Figure 3: Two peer routers (R5 and R6) cooperatively servicing four 2079 child routers (R1 - R4). 2081 For scalability purposes, a hierarchy of routers is used to transport 2082 messages from a sender to a receiver. Each layer of peer routers 2083 would have its own multicast group address for the exchange of 2084 Service Area Queries and Reports between the peer routers. However, 2085 routers in distinct subtrees need not know about the routers in other 2086 subtrees. Therefore, multicast group addresses will also differ 2087 between hierarchy subtrees. See figure 3. For instance, routers R1 2088 and R2 would share a multicast group and would know about each other. 2089 At the same time, routers R3 and R4 would share a different multicast 2090 group and would know about each other. However, routers R1 and R2 2091 would not know about R3 and R4, and vice versa. 2093 But how will the router know the location and number of its peer 2094 routers and who its parent router is? As mentioned before, the 2095 router consults its configuration file upon start-up. Included in 2096 this configuration file will be the the address of its parent router 2097 and the multicast group address that the peer routers will use. This 2098 peer multicast group address will be used in the same manner as the 2099 base station multicast group address. It will be used to send and 2100 receive Service Area Queries and Reports between the parent router 2101 and the peer routers. There is only one difference. When a router 2102 sends a Service Area Report, in addition to reporting its 2103 geographical service area, a router will include the multicast 2104 address of its children base stations. The reason for this is 2105 explained in the router-failure recovery scheme described below. 2107 3c-v. Routing Optimizations 2109 The optimization described here attempts to reduce the latency of a 2110 GPScast. It does so by reducing the the number of hops a packet must 2111 traverse before finding its destination. The intuition behind the 2112 idea is this: instead of going to the parent router and then to the 2113 sibling, simply go to the sibling directly. As an additional 2114 benefit, this method prevents the parent router from becoming a 2115 bottleneck or a point of failure in the routing scheme. 2117 In this optimization, when a router attempts to determine who will 2118 receive the GPS packet, it considers its peer routers as if they were 2119 also its children in the routing hierarchy. This means that the 2120 router will consider its service area to be the union of the service 2121 areas of its children and its peer routers. Also, when the 2122 destination polygon intersects the router's service area polygon, the 2123 router will forward a copy of the GPScast packet to any child or peer 2124 router whose geographic service area contains or touches the packet's 2125 GPS destination polygon. 2127 However, before it sends a copy of the packet to a peer router, it 2128 first finds the polygon: 2130 P = D /\ S 2132 where D stands for the packet's destination GPS polygon, S is the 2133 polygon representing the service area of the peer router, and P is 2134 the polygon that represents the intersection of D and S. The polygon 2135 P is substituted for the destination polygon D in the packet and only 2136 then is the packet forwarded to the peer router. This is necessary 2137 because the peer router will be using that same routing algorithm. 2138 Therefore, if the peer router receives a packet with the original 2139 destination polygon D, it will also route copies of the packet to all 2140 of its qualifying peer routers causing a chain of packet copies being 2141 bounced back and forth. 2143 3c-vi. Router-Failure Recovery Scheme 2144 In the case of a router failure, the system should be able to route 2145 around the failed router and continue to service GPScast messages. 2146 The responsibility of detecting whether a router has failed or not 2147 falls to the parent router. Using Figure 3 as an example router 2148 hierarchy, the parent router R5 periodically sends out Service Area 2149 Query IGPSMP messages on its children's multicast group address. 2150 Thus, the child routers R1 and R2 will both receive this query. 2151 Normally, both routers will respond with a Service Area Report 2152 message. This message contains a polygon describing their service 2153 areas and the multicast group address of their children. 2155 However, if a router, R1, does not respond to ten continuous queries, 2156 then it must be considered to have failed. Upon detecting this, the 2157 parent router R5 will send a Set Service Area message to the child 2158 router, R2 telling it to assume responsibility for the base stations 2159 underneath the failed R1 router. In this Set Service Area message, 2160 the parent router includes the multicast group address of R1's 2161 children. The R2 router uses this multicast address to learn the 2162 service areas and IP addresses of R1's children. The R2 router then 2163 issues a Service Area Report advertising its new enlarged service 2164 area responsibilities. All peer and parent routers will then update 2165 their routing tables to include this new information. When the 2166 failed router, R1, restarts, it will declare that it is alive and 2167 that it is again servicing its area. All routers will then again 2168 update their routing tables. 2170 In the case that there is no parent router, such as at the top of the 2171 routing hierarchy, then each peer router will keep track of its 2172 neighbors. If a neighbor router fails, then the first neighbor 2173 router to declare that it is taking over the base stations for the 2174 failed router will take responsibility. The rest continues as 2175 before. 2177 3c-vii. Domain Name Service Issues 2179 Domain Name Servers (DNS) could be used to facilitate the use of GPS 2180 geographic addressing for sites of interest. The aim is to describe 2181 specific geographic sites in a more natural and real-world manner 2182 using a postal-service like addressing method. Essentially, the DNS 2183 would resolve a postal-service like address, such as 2184 City_Hall.New_York_City.New_York, into the IP address of the GPS 2185 router responsible for that site. The GPS router would then route 2186 the message to all available recipients in the site. 2188 The DNS would be used when a message is sent using the 2189 site-code.city-code.state-code.country-code 2191 addressing scheme. The DNS would evaluate the address in reverse 2192 starting with the country code, then the state code, etc. This is 2193 the same method used currently by the IP DNS service to return IP 2194 addresses based on the country or geographic domains. 2196 4. Router Daemon and Host Library 2198 4a. GPS Address Library - SendToGPS() 2200 A library for GPS address routing will be constructed. The main 2201 routines contained in this library will be the SendToGPS() and 2202 RecvFromGPS() commands. SendToGPS() has the following syntax: 2204 SendToGPS(int socket, GPS-Address *address, char *message, int size) 2206 where socket is a previously created datagram socket, address is a 2207 filled GPS-Address structure with the following form: 2209 typedef _GPS-Address { 2210 enum { point, circle, polygon } type; 2211 char *mail-address; 2212 struct 2213 { 2214 enum { North, South, West, East } dir; 2215 int hours, minutes, seconds; 2216 } *points; 2218 } GPS-Address; 2220 and message and size specify the actual message and its size. The 2221 SendToGPS() routine will take the GPS-addressed message, encapsulate 2222 it in an IP packet, and then send it as a normal IP datagram. The 2223 message is encapsulated in the following manner: 2225 -------------------------------------------------------- 2226 | IP Header with destination address set to 240.0.0.0 | 2227 -------------------------------------------------------- 2228 | Sender Identifier | 2229 -------------------------------------------------------- 2230 | Address Type - Circle|Polygon | 2231 -------------------------------------------------------- 2232 | Actual GPS Address (see below) | 2233 -------------------------------------------------------- 2234 | Body of Message | 2235 -------------------------------------------------------- 2237 where the Sender Identifier would consist of a combination of the 2238 sender's process id, host IP address, and the center of the 2239 destination polygon. The Actual Address would be one of the 2240 following: 2242 circle - single GPS address and range measured in centiminutes. 2244 polygon - list of GPS addresses terminated by the impossible 2245 address: N 255 255 255. 2247 RecvFromGPS() has the following syntax: 2249 RecvFromGPS(int socket,GPS-Address *address,char *message,int size) 2251 where socket is a previously created datagram socket, address is an 2252 empty GPS-Address structure, and message and size specify message 2253 buffer and its size. 2255 4b. Establishing A Default GPS Router 2257 The default GPS router is determined using the unicast routing table 2258 found in the UNIX kernel. The local system administrator will have 2259 previously adjusted the table so that all GPScast messages are sent 2260 to the local GPS router. However, if there is no route for GPScast 2261 messages in the table, then all messages will, by default, be sent to 2262 the default gateway. If the default gateway does not support GPScast 2263 messages, then all attempts to send a GPScast will return an error. 2265 By default, all GPScast messages will initially have as their 2266 destination the class E address 240.0.0.0. A route will be added to 2267 the kernel routing table by the system administrator for this 2268 address. The route will specify the location of the local GPS 2269 router. The "route" command will be used to affect the routing table 2270 and it can be placed in the /etc/rc.local or /etc/rc.ip files so that 2271 it will take effect each time the computer is booted. For example, 2272 to specify that GPScast messages addressed to 240.0.0.0 should, by 2273 default, be sent to the router which resides on a computer on the 2274 same subnet with local address 128.6.5.53, use the following: 2276 /etc/route add host 240.0.0.0 128.6.5.53 0 2278 If the default destination for GPScast messages is a host that does 2279 not support GPS addressing, then Network Unreachable errors will be 2280 returned to any process attempting to route GPScasts through that 2281 host. 2283 4c. GPSRouteD 2285 In order to provide the capability of GPS address routing throughout 2286 an IPv4-based internetwork, special-purpose routers will be created 2287 to support GPS address routing on top of the current Internet. These 2288 routers, which will be called GPSRouteD, will use virtual point-to- 2289 point links called tunnels in order to connect two GPSRouteDs 2290 together over regular unicast networks. The tunnels work by 2291 encapsulating the GPS address messages in IP datagrams and then 2292 transmitting the message to the host on the other end of the tunnel. 2293 In this manner, the GPS address messages look like normal unicast 2294 packets to all IPv4 routers in between the two GPS address routers. 2295 At the end of the tunnel, the receiving GPSRouteD removes the GPS 2296 address message from the datagram and continues the routing process. 2298 By using tunnels, the GPS routers can be established as a virtual 2299 internetwork throughout the current Internet without regard for the 2300 physical properties of the underlying networks. Moreover, the use of 2301 tunnels means that the host on which the router daemon is running 2302 need not be connected to more than one subnet in order for the router 2303 to forward GPS messages. This virtual internetwork would be 2304 responsible for routing GPS address messages only. This virtual 2305 network, however, is not intended to be a permanent solution and is 2306 only intended to provide a means of supporting GPS address routing 2307 until it gains wider acceptance and support in the Internet 2308 infrastructure. 2310 4c-i. Configuration 2312 When a GPSRouteD initially executes, it first checks the file 2313 /etc/GPSRouteD.conf for configuration commands to add tunnel and 2314 multicast links to other GPS address routers. There are two kinds of 2315 configuration commands: 2317 multicast 2319 tunnel 2320 2322 The tunnel command is used to create a tunnel between the local host 2323 on which the GPSRouteD executes and a remote host on which another 2324 GPSRouteD executes. The tunnel must be set up in the GPSRouteD.conf 2325 files at both ends before it will be used. 2327 The multicast command tells the router which multicast addresses to 2328 join. These addresses will carry IGPSMP messages and replies. The 2329 router will use these IGPSMP messages to build up and keep current 2330 its own internal routing table. 2332 4d. Multicast Address Resolution Protocol (MARP) 2334 Of course, this begs the question, how will the individual computers 2335 know which multicast addresses to join? For example, an MH would 2336 have to join the multicast address of its current cell so that it can 2337 receive GPScast messages (using application-level filtering) or 2338 directions to join other multicast groups (using multicast 2339 filtering). We have designed a protocol called Multicast Address 2340 Resolution Protocol (MARP) that works the same way as Reverse Address 2341 Resolution Protocol (RARP). However, instead of returning the IP 2342 address of the MH, it will return multicast group address of the cell 2343 the MH is currently in. The MH would then join this multicast group. 2345 4e. Internet GPS Management Protocol (IGPSMP) 2347 The Internet GPS Management Protocol (IGPSMP) is used by GPS routers 2348 to report, query, and inform their router counterparts about their 2349 geographical service areas. The IGPSMP will also be used to verify 2350 that routers are correctly functioning. 2352 The vocabulary of IGPSMP will consist of six words: 2354 o set service area - Used by the parent router to set the 2355 geographic service area of a router. This is needed in 2356 order to automatically respond to router failure or new 2357 router boot-up. 2359 o confirm service area - confirms that a router has received 2360 its service area. 2362 o geographical service area query - This message will be used 2363 by a router to build up its geographical routing table. 2364 It is sent to all routers on the same level. 2366 o service area report - This message is sent in response to a 2367 query request. It contains a bounding closed polygon 2368 described using GPS coordinates which contains the service 2369 area for the router. 2371 o ping - This message is sent periodically to ascertain whether 2372 the router is currently functioning properly. Usually sent 2373 by the parent router in the hierarchy tree. 2375 o alive signal - Usually sent as a reply to the ping message. 2376 Used by a router to indicate that it is functioning 2377 correctly. It is also sent immediately after a router 2378 boots. 2380 All of IGPSMP messages will be sent on an all-routers multicast 2381 address for a particular hierarchy level. The exact multicast 2382 address can be set in the router configuration file. 2384 Note that for the GPS-Multicast routing scheme, the time-to-live 2385 value of the service area reports will be varied in order to control 2386 the distribution of the information. In GPS-Multicast routing, only 2387 the multicast group membership for very large partitions will be 2388 distributed throughout the country. Smaller partition may only be 2389 distributed to neighbor routers. 2391 5. Working Without GPS Information 2393 5a. Users Without GPS Modules 2395 Mobile users without GPS modules can still participate - though at a 2396 very reduced level. When an MH enters a cell, it can use an MARP to 2397 discover the local multicast group for that cell or atom. As the 2398 user roams from cell to cell, the mobile host can keep track of the 2399 current cell that the user is in and adds or drops the multicast 2400 groups pertaining to those cells. The user's GPS address can be set 2401 to be the center of the current cell. 2403 5b. Buildings block GPS radio frequencies. What then? 2405 Each room can have a radio beacon placed on the ceiling. The beacon 2406 will be weak enough so that it will not penetrate walls. Each radio 2407 beacon will have its own GPS-address associated with it which it will 2408 broadcast. When a mobile user enters a room, his MH will detect the 2409 beacon and read the beacon's GPS address. The GPS-address of the MH 2410 will be set to the GPS-address of the beacon. The MH will then use 2411 this beacon's GPS address in order to perform any message filtering 2412 that it needs to do. Now the mobile user can have a GPS-address 2413 associated with him even though he is indoors and his GPS-module is 2414 useless. 2416 6. Application Layer Solution 2418 In this subsection we sketch a third solution which relies more 2419 heavily on the DNS. 2421 In the application layer solution the geographic information is added 2422 to the DNS which provides the full directory information down to the 2423 level of the IP address of each base station and its area of coverage 2424 represented as a polygon of coordinates. 2426 A new first level domain - "geographic" is added to the set of first 2427 level domains. The second level domain names include states, the 2428 third, counties and finally, the fourth: polygons of coordinates, or 2429 so called points of interests. We can also allow, polygons to occur 2430 as elements of second, third domains to enable sending messages to 2431 larger areas. 2433 Thus a typical geographic address can look like 2435 city-hall-Palo-Alto.San-Mateo-County.California.geographic 2437 or 2439 Polygon.San-Mateo-County.California.geographic 2441 where Polygon is a sequence of coordinates. 2443 This geographic address is resolved in a similar way as the standard 2444 domain addresses are resolved today into a set of IP addresses of 2445 base stations which cover that geographic area. There are several 2446 possibilities here: 2448 a. A set of unicast messages is sent to all base stations 2449 corresponding to the IP addresses returned by the DNS. Each base 2450 station then forwards the message using either of the two last link 2451 solutions: application level or network level filtering. 2453 b. All the base stations join the temporary multicast group for the 2454 geographic area specified in the message. In this way we may avoid 2455 sending the same message across the same link several times. Thus, 2456 after the set of relevant base stations is determined by the DNS, the 2457 temporary multicast group is established and all packets with that 2458 multicast address are sent on that multicast address. 2460 c. Only one, central to the polygon base station is returned by the 2461 DNS just as in the IP unicast solution. However that "central" base 2462 station will have to forward messages to the other base stations 2463 within the polygon. 2465 Notice that we should distinguish between "small area" and "wide 2466 area" geographic mail. The "small area" mail will be most common and 2467 will most likely involve just one base station, favoring a simple 2468 form of solution (a). 2470 7. Reliability 2472 Should the geographic messages be acknowledged? 2474 Since we have no control if users are present in the target 2475 geographic area where the mail is distributed we do not see a need 2476 for individual acknowledgments from the message recipients. However, 2477 we believe that the base stations (MSS) covering the target area of 2478 geographic mail should acknowledge the messages. 2480 Typically only a few base stations will be involved since typically 2481 we will not cover very broad geographic areas anyway. We assume that 2482 the base stations, additionally to forwarding the the messages on 2483 their wireless interfaces will buffer them, either to periodically 2484 multicast them (emergency response) or to provide them to users who 2485 just entered a cell and download the "emergency stack" of messages 2486 for that area as a part of the service hand-off protocol. 2488 8. Security Considerations 2490 Some method of determining who has permission to send messages to a 2491 large geographical area is needed. For instance, perhaps only the 2492 mayor of New York City has permission to send a message to all of New 2493 York City. 2495 9. References 2496 S. Deering. Host Extensions for IP Multicasting. RFC 1112, (August 2497 1989) 2499 S. Deering. Multicast Routing in a Datagram Internetwork. Ph.D. 2500 Thesis, Stanford University, (December 1991) 2502 J. O'Rourke, C.B. Chien, T. Olson, and D. Naddor, A new linear 2503 algorithm for intersecting convex polygons, Computer Graphics and 2504 Image Processing 19, 384-391 (1982). 2506 J. Ioannidis, D. Duchamp, and G. Q. Maquire. IP-Based Protocols for 2507 Mobile Internetworking. Proc. of ACM SIGCOMM Symposium on 2508 Communication, Architectures and Protocols, pages 235-245, 2509 (September, 1991) 2511 10. Author's Address 2513 Tomasz Imielinski and Julio C. Navas 2514 Computer Science Department 2515 Busch Campus 2516 Rutgers, The State University 2517 Piscataway, NJ 2518 08855 2520 Phone: 908-445-3551 2521 EMail: {imielins,navas}@cs.rutgers.edu