File: rfc2009.txt

package info (click to toggle)
doc-rfc 20181229-2
  • links: PTS, VCS
  • area: non-free
  • in suites: buster
  • size: 570,944 kB
  • sloc: xml: 285,646; sh: 107; python: 90; perl: 42; makefile: 14
file content (1515 lines) | stat: -rw-r--r-- 66,229 bytes parent folder | download | duplicates (5)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515






Network Working Group                                 T. Imielinski
Request for Comments: 2009                                 J. Navas
Category: Experimental                           Rutgers University
                                                      November 1996


                    GPS-Based Addressing and Routing

Status of this Memo

   This memo defines an Experimental Protocol for the Internet
   community.  This memo does not specify an Internet standard of any
   kind.  Discussion and suggestions for improvement are requested.
   Distribution of this memo is unlimited.

IANA Note:

   This document describes a possible experiment with geographic
   addresses.  It uses several specific IP addresses and domain names in
   the discussion as concrete examples to aid in understanding the
   concepts.  Please note that these addresses and names are not
   registered, assigned, allocated, or delegated to the use suggested
   here.

Table of Contents

   1.      Introduction......................................    2
   1b.             General Architecture......................    3
   1c.             Scenarios of Usage: Interface Issues......    3
   2.      Addressing Model..................................    4
   2a.             Using GPS for Destination Addresses.......    5
   3.      Routing...........................................    7
   3a.              GPS Multicast Routing Scheme (GPSM)......    7
   3a-i.                   Multicast Trees...................    8
   3a-ii.                  Determining the GPS Multicast
                           Addressing........................   10
   3a-iii.                 Building Multicast Trees..........   11
   3a-iv.                  Routing...........................   12
   3a-v.                   DNS Issues........................   12
   3a-vi.                  Estimations.......................   12
   3b.              "Last Mile"  Routing.....................   13
   3b-i.                   Application Level Filtering.......   13
   3b-ii.                  Multicast Filtering...............   13
   3b-iii.                 Computers on Fixed Networks.......   14
   3c.              Geometric Routing Scheme (GEO)...........   14
   3c-i.                   Routing Overview..................   14
   3c-ii.                  Supporting Long-Duration GPScasts.   16
   3c-iii.                 Discovering A Router's Service Area  17



Imielinski & Navas            Experimental                      [Page 1]

RFC 2009            GPS-Based Addressing and Routing       November 1996


   3c-iv.                  Hierarchical Router Structure and
                           Multicast Groups..................   18
   3c-v.                   Routing Optimizations.............   19
   3c-vi.                  Router-Failure Recovery Scheme....   19
   3c-vii.                 Domain Name Service Issues........   20
   4.      Router Daemon and Host Library....................   21
   4a.             GPS Address Library - SendToGPS().........   21
   4b.             Establishing A Default GPS Router.........   22
   4c.             GPSRouteD.................................   22
   4c-i.                  Configuration......................   23
   4d.             Multicast Address Resolution Protocol (MARP) 23
   4e.             Internet GPS Management Protocol (IGPSMP).   24
   5.      Working Without GPS Information...................   25
   5a.             Users Without GPS Modules.................   25
   5b.             Buildings block GPS radio frequencies
                   What then?................................   25
   6.      Application Layer Solution........................   25
   7.      Reliability.......................................   26
   8.      Security Considerations...........................   27
   9.      References........................................   27
   10.     Authors' Addresses................................   27

1.      Introduction

   In the near future GPS will be widely used allowing a broad variety
   of location dependent services such as direction giving, navigation,
   etc. In this document we propose a family of protocols and addressing
   methods to integrate GPS into the Internet Protocol to enable the
   creation of location dependent services such as:

     o     Multicasting selectively only to specific geographical
           regions defined by latitude and longitude. For example,
           sending an emergency message to everyone who is currently
           in a specific area, such as a building or train station.

     o     Providing a given service only to clients who are within a
           certain geographic range from the server (which may be mobile
           itself), say within 2 miles.

     o     Advertising a given service in a range restricted way, say,
           within 2 miles from the server,










Imielinski & Navas            Experimental                      [Page 2]

RFC 2009            GPS-Based Addressing and Routing       November 1996


     o     Providing contiguous information services for mobile users
           when information depends on the user's location. In
           particular providing location dependent book-marks, which
           provides the user with any important information which
           happens to be local (within a certain range) possibly
           including other mobile servers.

   The solutions which we present are flexible (scalable) in terms of
   the target accuracy of the GPS. We also discuss cases when GPS cannot
   be used (like inside buildings).

   The main challenge is to integrate the concept of physical location
   into the current design of the Internet which relies on logical
   addressing.  We see the following general families of solutions:

      a) Unicast IP routing extended to deal with GPS addresses

      b) GPS-Multicast solution

      c) Application Layer Solution using extended DNS

   The first two solutions are presented in this memo. We only sketch
   the third solution.

1b. General Architecture

   We will assume a general cellular architecture with base stations
   called Mobile Support Stations (MSS). We will consider a wide variety
   of cells, including outdoor and indoor cells. We will discuss both
   cases when the mobile client has a GPS card on his machine and cases
   when the GPS card does not work (i.e. - inside buildings).

   We will assume that each MSS covers a cell with a well defined range
   specified as a polygon of spatial coordinates and that the MSS is
   aware of its own range.

1c. Scenarios of Usage and Interface Issues

   Below, we list some possible scenarios of usage for the geographic
   messaging.

   Consider an example situation, of an area of land near a river.
   During a severe rain storm, the local authorities may wish to send a
   flood warning to all people living within a hundred meters of the
   river.






Imielinski & Navas            Experimental                      [Page 3]

RFC 2009            GPS-Based Addressing and Routing       November 1996


   For the interface to such messaging system we propose to use a zoom-
   able map similar to the U.S. Census Bureau's Tiger Map Service.  This
   map would allow a user to view a geographical area at varying degrees
   of magnitude.  He could then use a pointing device, such as a mouse,
   to draw a bounding polygon around the area which will receive the
   message to be sent.  The computer would then translate the drawn
   polygon into GPS coordinates and use those coordinates when sending
   and routing the message.  Geographical regions specified using this
   zoom-able map could be stored and recalled at a later time.  This
   zoom-able map is analogous to the IP address books found in many
   email programs.

   To continue with the above example, local officials would call up a
   map containing the river in danger of overflowing.  They would then
   hand-draw a bounding polygon around all of the areas at least a
   hundred yards from the river.  They would specify this to be the
   destination for a flood warning email to all residents in the area.
   The warning email would then be sent. Similar applications include
   traffic management (for example, reaching vehicles which are stuck in
   traffic) and security enforcement.

   Other applications involve general client server applications where
   servers are selected on the basis of the geographic distance. For
   example, one may be interested in finding out all car dealers within
   2 miles from his/her location.  This leads to an extension of the Web
   concept in which location and distance play important roles in
   selecting information. We are currently in the process of
   implementing location dependent book-marks (hot lists) in which pages
   associated with static and mobile servers which are present within a
   certain distance from the client are displayed on the client's
   terminal.

2.      Addressing Model

   Two-dimensional GPS positioning offers latitude and longitude
   information as a four dimensional vector:

              <Direction, hours, minutes, seconds>

   where Direction is one of the four basic values: N, S, W, E; hours
   ranges from 0 to 180 (for latitude) and 0 to 90 for longitude, and,
   finally, minutes and seconds range from 0 to 60.

   Thus <W, 122, 56, 89> is an example of longitude and <N, 85, 66, 43>
   is an example of latitude.






Imielinski & Navas            Experimental                      [Page 4]

RFC 2009            GPS-Based Addressing and Routing       November 1996


   Four bytes of addressing space (one byte for each of the four
   dimensions) are necessary to store latitude and four bytes are also
   sufficient to store longitude. Thus eight bytes total are necessary
   to address the whole surface of earth with precision down to 0.1
   mile!  Notice that if we desired precision down to 0.001 mile (1.8
   meters) then we would need just five bytes for each component, or ten
   bytes together for the full address (as military versions provide).

   The future version of IP (IP v6) will certainly have a sufficient
   number of bits in its addressing space to provide an address for even
   smaller GPS addressable units.  In this proposal, however, we assume
   the current version of IP (IP v4) and we make sure that we manage the
   addressing space more economically than that.  We will call the
   smallest GPS addressable unit a GPS-square.

2a.     Using GPS for Destination Addresses

   A destination GPS address would be represented by one of the
   following:

     o     Some closed polygon such as:

                   circle( center point, radius )

                   polygon( point1, point2, point3, ... , pointn)

           where each point would be expressed using GPS-square
           addresses.  This notation would send a message to anyone
           within the specified geographical area defined by the closed
           polygon.

     o     site-name as a geographic access path

           This notation would simulate the postal mail service.  In
           this manner, a message can be sent to a specific site  by
           specifying its location in terms of real-world names
           such as the name of a specific site, city, township,
           county, state, etc.  This format would make use of the
           directory service detailed later.












Imielinski & Navas            Experimental                      [Page 5]

RFC 2009            GPS-Based Addressing and Routing       November 1996


   For example, if we were to send a message to city hall in Fresno,
   California, we could send it by specifying either a bounding polygon
   or the mail address.  If we specify a bounding polygon, then we could
   specify the GPS limits of the city hall as a series of connected
   lines that form a closed polygon surrounding it.  Since we have a
   list of connected lines, we just have to record the endpoints of the
   lines.  Therefore the address of the city hall in Fresno could look
   like:

     polygon([N 45 58 23, W 34 56 12], [N 23 45 56, W 12 23 34], ... )

   Alternatively, since city hall in Fresno  is a well-defined
   geographical area, it would be simpler to merely name the
   destination. This would be done by specifying "postal-like" address
   such as city_hall.Fresno.California.USA.

   For "ad hoc" specified areas such as, say a quad between 5th and 6th
   Avenue and 43 and 46 street in New York, the polygon addressing will
   be used.

   Unfortunately, we will not be able to assume that we have enough
   addressing space available in the IP packet addressing space to
   address all GPS squares. Instead we will propose a solution which is
   flexible in terms of the smallest GPS addressable units which we call
   atoms.  In our solution, a smaller available addressing space (in the
   IP packet) will translate into bigger atoms.  Obviously, we can use
   as precise addressing as we want to in the body of the geographic
   messages - the space limitations apply only to the IP addressing
   space.

   By a geographic address we mean an IP address assigned to a
   geographic area or point of interest.  Our solution will be flexible
   in terms of the geographic addressing space.

   Below, we will use the following two terms:

     o     Atoms: for smallest geographic  areas which have
           geographic address.

           Thus, atoms could be as small as GPS squares but could be
           larger

     o     Partitions: These are larger, geographical areas, which will
           also have a geographic address. A state, county, town etc.
           may constitute a partition. A partition will contain a number
           of atoms.





Imielinski & Navas            Experimental                      [Page 6]

RFC 2009            GPS-Based Addressing and Routing       November 1996


   Here are some examples of possible atoms and partitions:

     o     A rectangle, defined by truncating either longitude or
           latitude part of the GPS address by skipping one or more
           least significant digits

     o     A circle, centered in a specific GPS address with a
           prespecified radius.

     o     Irregular shapes such as administrative domains: states,
           counties, townships, boroughs, cities etc

   Partitions and Atoms (which are of course special atomic partitions)
   will therefore have geographic addresses which will be used by
   routers. Areas of smaller size than atoms, or of "irregular shape"
   will not have corresponding geographic addresses and will have to
   handled with the help of application layer.

3.      Routing

   Let us now describe the suggested routing schemes responsible for
   delivering a message to any geographical destination.

   We will distinguish between two legs of the connection from the
   sender to the receiver: the first leg from the sender to the MSS
   (base station) and the second leg from the MSS to the receiver
   residing in its cell.  Our two solutions will differ on the first leg
   of the connection and use the same options for the second leg, which
   we call "last mile".

3a.     GPS-Multicast Routing Scheme

   Here, we discuss the first leg of routing: from the sender to the
   MSS. We start with the multicasting solution.

   Each partition and atom is mapped to a multicast address. The exact
   form of this mapping is discussed further in this subsection.  We
   first sketch the basic idea.













Imielinski & Navas            Experimental                      [Page 7]

RFC 2009            GPS-Based Addressing and Routing       November 1996


   This solution provides flexible mix of the multicast and application
   level filtering for the geographic addressing.  The key idea here is
   to approximate the addressing polygon of the smallest partition which
   contains it and using the multicast address corresponding to that
   partition as the IP address of that message. The original polygon is
   a part of the packet's body and the exact matching is done on the
   application layer in the second leg of the route.

   How is the multicast routing performed?

3a-i.           Multicast Trees

   The basic idea for the first level of routing using multicast is to
   have each base station join multicast groups for all partitions which
   intersect its range.  Thus, MSS is not only aware of its own range
   but also has a complete information about system defined partitions
   which its range intersects. This information can be obtained upon MSS
   installation, from the geographic database stored as a part of DNS.

   If the proper multicast trees are constructed (using for example link
   state multicast protocol) than the sender can simply determine the
   multicast address of the partition which covers the original polygon
   he wants to send his message to, use this multicast address as the
   address on the packet and put the original polygon specification into
   the packet content.  In this way, multicast will assure that the
   packet will be delivered to the proper MSS.

   Example

   For instance the MSS in New Brunswick may have its range intersect
   the following atoms and partitions: Busch, College Avenue, Douglass
   and Livingston Campuses of Rutgers University (atoms), New Brunswick
   downtown area (atom), the Middlesex county partition and the NJ state
   partition. Each of these atoms and partitions will be mapped into a
   multicast address and the New Brunswick's MSS will have to join all
   such multicast groups.

   The message will be then specified and sent as follows:

   The user will obtain the map of the New Brunswick area possibly from
   the DNS extended properly with relevant maps. He will specify the
   intended destination by drawing a polygon on the map which will be
   translated into the sequence of coordinates. In the same time the
   polygon will be "approximated" by the smallest partition which
   contains that polygon. The multicast address corresponding to that
   partition will be the IP address for packets carrying our message.
   The exact destination polygon will be a part of each packet's body.
   In this way the packet will be delivered using multicast routing to



Imielinski & Navas            Experimental                      [Page 8]

RFC 2009            GPS-Based Addressing and Routing       November 1996


   the set of MSS which are members of the specified multicast group
   (that is all MSS whose ranges intersect the given partition). Each
   such MSS now will follow the "last mile" routing which is described
   in detail, further in the proposal. Briefly speaking, the MSS could
   then multicast the message further on the same multicast address and
   the client will perform the final filtering o application layer,
   matching its location (obtained from GPS) with the polygon specified
   in the packet's body.  Other solutions based entirely on multicasting
   are also possible as described below.

   End_Example

   However, things cannot be as simple as described.  For such a large
   potential number of multicast groups if we build entire multicast
   trees, the routing tables could  be too large.  Fortunately it is not
   necessary to build complete multicast trees. Indeed, it in not
   important to know precise location of each atom in California, from a
   remote location, say in NJ.

   Thus, we modify our simple solution by implementing the following
   intuition:

   The smaller is the size of the partition (atom) the more locally is
   the information about that partition (atom) propagated.

   Thus, only multicast group membership for very large partitions will
   be propagated across the whole country.

   For example, a base station in Menlo Park, California can intersect
   several atoms ) and several larger  which cover Menlo Park, such say
   a partition which covers the entire San Mateo county, next which
   cover the entire California and finally next which may cover the
   entire west coast.  This base station will have to join multicast
   groups which correspond to all these rectangles. However, only the
   information about multicast group corresponding to the West Coast
   partition will be propagated to the East Coast routers.

   However, a simple address aggregation scheme in which only a "more
   significant portion" of address propagates far away would not work.
   Indeed, in this case a remote router, say in NJ, could have several
   aggregate links leading to California - in fact, in the worst case,
   all its links could point to California since it could have received
   a routing information to some location in California on any of those
   links.

   To avoid this, for each partition we distinguish one or a few MSS
   which act as designated router(s) for that partition.  For example,
   the California partition, may have only three designated routers, one



Imielinski & Navas            Experimental                      [Page 9]

RFC 2009            GPS-Based Addressing and Routing       November 1996


   in Eureka, another in Sacramento and yet another in LA. Only the
   routing entries from the designated routers would be aggregated into
   the aggregate address for California. Information coming from other
   city routers will simply be dropped and not aggregated at all. This,
   in addition to a standard selection of the shortest routes, would
   restrict the number of links which lead to an aggregate address.  In
   particular, when there is only one designated router per partition,
   there would only be one aggregate link in any router. This could lead
   to non-optimal routing but will solve the problem of redundant links.

   Even with a designated routers, it may happen that the same packet
   will arrive at a given base station more than once due to different
   alternative routes. Thus, a proper mechanism for discarding redundant
   copies of the same packet should still be in place.  In fact, due to
   the possible intersections between ranges of the base stations the
   possibility of receiving redundant copies of the same packets always
   exist and has to be dealt with as a part of any solution.

3a-ii.         Determining the geographic Multicast Addressing

   Here we describe more specifically, the proposed addressing scheme
   and the corresponding routing.

   The addressing will be hierarchical.  We will use the following
   convention - each multicast address corresponding to a partitions or
   an atoms will have the following format:

                            1111.GPS.S.C.x

   where GPS is the specific code corresponding to the geographic
   addressing subspace of the overall multicast addressing space. The S,
   C and x parts are described below:

      S  - Encoding of the state.
           Each state partition will have the address S/0/0.

      C  - County within a state.
           Each county partition having the address S/C/0.

      x  - Atom  within a county.

   where 0's refer to the sequences of 0 bits on positions corresponding
   to the  "C part"  and "x part" of address.

   For example if GPS part is 6 bit,s which gives 1/64 of existing
   multicast addresses to the geographic addressing we have 22 bits
   left.  The S part will take first 6 bits, C part next 6 bits (say)
   and then the next 10 bits encode  different atoms (within a county).



Imielinski & Navas            Experimental                     [Page 10]

RFC 2009            GPS-Based Addressing and Routing       November 1996


   Thus, in our terminology the proposed addressing scheme has two types
   of partitions: states and counties.

   We will assume that the GPS network will consist of all base stations
   (MSS) in addition the rest of the fixed network infrastructure. The
   designated GPS routers however, will only be selected from the
   population of MSS.  Specifically, there will be state dedicated and
   county dedicated routers.

   The concept of the designation will be implemented as follows.  From
   the set of all MSS, only certain MSS will play a role of designated
   routers for county  and state partitions.  Non-designated MSS will
   only join multicast groups which correspond to the GPS atoms but not
   GPS partitions that they intersect. The MSS which is a designated
   router for a county partition will join the multicast group of the
   county in which it is located, but not the state. Finally the state
   designated router will also join the multicast address corresponding
   to the state it is located in.

3a-iii.  Building Multicast Trees

   We assume that each router has geographic information attached to it
   - in the same format as we use for multicast mapping, S/C/x - it
   encodes the atom that contains the router.

   The multicast tree is built by a router propagating its multicast
   memberships to the neighboring routers. A given router will only
   retain certain addresses though, to follow the intuition of not
   retaining a specific information which is far away.

   This is done as follows: the router (not necessarily the MSS based
   router) with the address S/C/x will only retain addresses about
   S'/0/0, S/C'/0 for S' and C' different from S and C and S/C/x for all
   x.  Thus, it will drop all the addresses of the form S'/C'/y for all
   S' different that S except those with C'=0 and y=0, as well as all
   the addresses of the form S/C'/y with C' different from C except
   those with y=0.  Hence, these addresses will not be forwarded any
   further either.

   Thus, notice that only the information coming from designated routers
   will be forwarded further away, since the non-designated routers are
   not allowed to join the multicast groups which correspond to the
   states and counties. Consequently, their multicast membership
   information will be not be propagated.

   In this way a router at S/C/x will not bother about specific
   locations within S'/C'/y since they are "too far".




Imielinski & Navas            Experimental                     [Page 11]

RFC 2009            GPS-Based Addressing and Routing       November 1996


   Notice that this service may not be provided everywhere so we may not
   have to use all multicast addresses even within those assigned for
   geographic addresses.

   Notice also that all of this is flexible - if we have more multicast
   addresses available (IP v 6) we will get more precise addressing due
   to smaller atoms.

3a-iv.           GPS Routing

   Given a packet we always look for the "closest" match in the routing
   table. If there is a complete match we follow such a link, if not we
   follow the address with the x-part 0'd in (county address) if there
   is none with the county which agrees with the destination county than
   we look at the entry which agrees with the state part of the
   destination address.

3a-v.          DNS Issues

   How does the client find out the multicast address on which the
   packet is to be sent?  We assume that the local name server has the
   complete state/county hierarchy and that each county map can be
   provided possibly with the "grid" of atoms and partitions already
   clearly marked.

   Points of interests within a county can be attached multicast address
   just as atoms. Then a given base station would have to join multicast
   groups of the points of interests that it covers.

   The final stage is for the receiver to look at the polygon (point of
   interest) which is encoded in the body of the multicast packet and
   decide on the basis of its own GPS location if this packet is to be
   received or not. Doing it on the application layer simplifies many
   routing issues. There is a tradeoff, however, specially when we have
   very short S/C/x addresses and base stations which do not cover the
   given polygon in fact are reached unnecessarily.  This may happen and
   it needs to be determined what is the number of the multicast
   addresses which are necessary to reduce this "false" alarms to the
   minimum.

3a-vi.                Estimations

   Assume average cell size of, say, 2km x 2km and the average state
   size: say 200,000 square km, the average county size: say 4,000
   square km.

   A reasonable size of the atom  is around the size of the cell since
   then we do not hit wrong cells too often.



Imielinski & Navas            Experimental                     [Page 12]

RFC 2009            GPS-Based Addressing and Routing       November 1996


   Therefore we need the x addressing part of the S/C/x to encode
   4,000/4 cells: 1.000 atoms. Thus we need 10 bits for x part. With 6
   bits for the state and 6 bits for the county that gives 22 bits which
   is 1/64 of the total IP v4 multicast addressing space.

   With IPv6 we will have, of course, much more addressing space which
   we can use for the GPS multicast routing.

3b.  "Last Mile"  Routing

   Multicasting will be used for the last mile routing in both our
   solutions (i.e the one just discussed and the geometric routing
   solution described next), but in different ways.

3b-i.           Application Level Filtering

   The MSS will forward the geographic message on its wireless link
   under a multicast address. This multicast address will either be the
   same for all locations in the range of the MSS's cell or, there will
   be several addresses corresponding to atoms which intersect the given
   cell. Additionally, a complete GPS address (for example in the form
   of the polygon) will be provided in the body of the packet and the
   exact address matching will be performed on the application layer.
   The receiver, knowing its GPS position uses it to match against the
   polygon address. The GPS position can be obtained by the receiver
   either from the GPS card or, indoors, from the indoor base station
   which itself knows its GPS position as a part of configuration file.

3b-ii.          Multicast Filtering

   In multicast level filtering, the base station assigns a temporary
   multicast address to the addressing polygon in a message.  It will
   send out a directive on the cell's specially assigned multicast
   address. All mobile clients who reside in that cell are members of
   that special multicast group (one per MSS). The directive sent by the
   MSS will contain the pair consisting of  the temporary multicast
   address together with the polygon. To improve the reliability this
   message will be multicast several times. The clients, knowing their
   GPS positions will than join the temporary multicast groups if their
   current locations are within the advertised polygon.  The MSS will
   then send out the real message using the temporary multicast address.

   The temporary multicast address would be cached for a period of time.
   If more packets for the same polygon arrive in a short period of
   time, they will be sent out on the same multicast address. If not,
   then the multicast address is dropped and purged from the cache.
   Filtering on the client's station is then performed entirely on the
   IP level. This solution introduces additional delay (needed to join



Imielinski & Navas            Experimental                     [Page 13]

RFC 2009            GPS-Based Addressing and Routing       November 1996


   the temporary multicast group) but reduces the number of irrelevant
   packets received by the client. This especially important for very
   long messages.

3b-iii.         Computers on Fixed Networks

   Fixed-network computers should also monitor all of the mandatory
   multicast addresses for their site and GPS square.  In this manner,
   the fixed computers will also receive messages sent to specific GPS-
   addresses.

   Modified base stations would still be in charge of multicasting the
   messages to the computers.  These base stations would have the same
   GPS-routing functionality as the mobile computer base stations.
   Their main difference would be that the mobile computer base stations
   would use radio frequencies to multicast their messages and the fixed
   network base stations use the local Ethernet or Token Ring network.

   The next scheme differs from the GPS multicast scheme described above
   only on the first leg of the route, from the sender to the MSS. The
   "last mile" from the MSS to the final destination will have the same
   options as described above.

3c.             Geometric Routing Scheme (GEO)

   The Geometric Routing Scheme (GEO) uses the polygonal geographic
   destination information in the GPScast header directly for routing.
   GEO routing is going to be implemented in the Internet Protocol (IP)
   Network layer in a manner similar to the way multicast routing was
   first implemented.  That is, a virtual network which uses GPS
   addresses for routing will be overlayed onto the current IP
   internetwork.  We would accomplish this by creating our own GPS-
   address routers.  These routers would use tunnels to ship data
   packets between them and between the routers and base stations.

3c-i.           Routing Overview

   Sending a GPScast message involves three steps: sending the message,
   shuttling the message between routers, and receiving the message.

   Sending a GPScast message is very similar to sending a UDP datagram.
   The programmer would use the GPScast library routine SendToGPS().
   Among other parameters, this routine will accept the GPS polygonal
   destination address and the body of the message.  The SendToGPS()
   routine will encapsulate the GPScast message in a UDP datagram and
   send it to the class E address 240.0.0.0.  Previously, the system
   administrator will have specified in the /etc/rc.local or /etc/rc.ip
   file a route command that will specify that packets with the address



Imielinski & Navas            Experimental                     [Page 14]

RFC 2009            GPS-Based Addressing and Routing       November 1996


   240.0.0.0 will instead be sent to the address of the local GPS
   router.  This will have the effect of sending the datagram to the
   nearest GPS router.

   Before explaining how the GPS routers shuttle the GPScast message to
   its destination, an introduction to routers and their different parts
   is in order.  For scalability purposes, GPS routers are arranged in a
   hierarchical fashion.  Each layer would correspond to a distinct
   geographic area, such as a state or a city.  At the top would be
   country-wide routers in charge of moving messages from one end of the
   country to another.  At the bottom would be campus or department
   routers in charge of moving messages between the base stations.  See
   Figure 1.


                                   Country-Router(s)
                                   /              \
                           State-Router(s)
                           /             \
                     City-Router(s)
                      /      \
                Router        Router
               /  |   \      |    \
           Base  Base  Base   Base  Base

   Figure 1: Hierarchy of routers.

   A GPS router essentially consists of three parts: a service area
   table containing the geographic area serviced by the router and each
   of its hierarchical children, a hashed cache of previous actions, and
   a table containing the IP addresses of at least the router's children
   and the router's parent.  In the case of a bottom-layer campus
   router, the service area table will contain polygons describing the
   geographic reach of each child base station's cell.  The polygon
   created from the union of all of the router's child base stations'
   polygons defines the service area of the router.

   Once the datagram arrives at a GPS router, the router strips the
   datagram off, thereby, leaving it with the original GPScast message.
   First the router must determine if it services any part of the area
   of the destination polygon.  To do this, the router finds the
   intersection between the destination polygon and the polygon
   describing the router's service area.  The polygon intersection
   algorithm used is described by O'Rourke in his paper, A New Linear
   Algorithm for Intersecting Convex Polygons.  This algorithm requires
   order N-squared time in the worst case.  If the intersection result
   is null, then the router simply sends the message to its parent
   router.



Imielinski & Navas            Experimental                     [Page 15]

RFC 2009            GPS-Based Addressing and Routing       November 1996


           ------ Destination Polygon
           | A  |
       --------------
       |   | B  |   | Router's Service Area Polygon
       --------------
           | C  |
           ------

   Figure 2: Polygon Difference

   However, if the result is not null, then the router does service the
   area described by the intersection polygon.  The router now subtracts
   its service area from the destination polygon and sends the rest to
   it's parent router.  This subtraction step is actually a by-product
   of the intersection algorithm.  Using the example in Figure 2, the
   destination polygon and the router's service area polygon intersect
   at the region labeled B.  Therefore, the router will subtract out the
   B section and send the remaining sections A and C to its parent
   router.

   Continuing with the example, the router now uses the intersection
   polygon B to to determine which base station (or stations) will
   receive the GPScast message.  The router finds the intersection
   between the region B and the polygon of each base station's cell.
   Those base station polygons which intersect the region B will be sent
   the GPScast message.  Processes on Mobile Hosts serviced by these
   base stations will now use the routine RecvFromGPS() to receive the
   GPScast message.

3c-ii.  Supporting Long-Duration GPScasts

   Most likely, there will be a need to support sending real-time
   continuous media to a GPS destination.  This continuous media could
   be an audio GPScast or a video GPScast.  This would require that
   jitter be reduced in order to minimize disturbing artifacts in the
   audio or video playback.  Continually checking the destination
   geometry of each packet would incur unnecessary delays and may
   promote jitter.

   Therefore, the router will keep a hashed cache of the latest GPScast
   packets and their destinations.  Each cache item will be hashed using
   the Sender Identification included in the header of GPScast messages
   as the key.  Each cache item will contain a time stamp and a list of
   the next hops for that GPScast.  When the time stamp exceeds a
   certain limit, then the cache item will be dropped.  The list of next
   hops is a list of the IP addresses of the base stations, peer
   routers, and parent router which are to receive a copy of the GPScast
   messages.



Imielinski & Navas            Experimental                     [Page 16]

RFC 2009            GPS-Based Addressing and Routing       November 1996


   When a router receives a GPScast packet, it will use the incoming
   packet's Sender Id as a key into the hashed cache.  If this is not
   the first packet to arrive for this destination and if the timer on
   the hash table entry has not yet expired, then the hashed cache will
   return a list of all of the destination addresses to which copies of
   the packet must be sent.  Copies of the packet are sent to all of
   these destinations and the hash entry's time stamp is updated.

   If no hash table entry is found (i.e.- this is the first packet
   encountered for this destination address), then the normal geometry
   checking routine would take over.  A new cache entry is made
   recording all of the next-hop destination addresses of the GPScast.
   In this manner, if several other packets with the same GPS
   destination follow this first packet, the router can use the hash
   table to look-up the destination base stations instead of calculating
   it using geometry.

3c-iii.          Discovering A Router's Service Area

   When the router is initiated, it will consult its configuration file.
   One of the items it will find in the file will be the multicast
   address of the base station group to which all of its child base
   stations are members.  The router will join this group and then send
   out Service Area Query messages to this multicast group periodically
   to discover and to refresh its knowledge of its children base
   stations and the geographical areas serviced by them.

   Queries are issued infrequently (no more than once every five
   minutes) so as to keep the IGPSMP overhead on the network very low.
   However, since the query is issued using unreliable multicast
   datagrams, there is a chance that some base stations may not receive
   the query.  This is important in two cases: when a child node fails
   and when a router first boots up.  The case of a failed child node
   will be explained later.  However, when a router first boots up, it
   can issue several queries in a small amount of time in order to
   guarantee that base stations will receive the query and to,
   therefore, build up its knowledge about its child base stations
   quickly.

   Base stations respond to a Service Area Query by issuing a Service
   Area Report.  This report is issued on the same multicast group
   address that all of the base stations have joined.  The report
   contains the geographical service area of the base station.  In order
   to avoid a sudden congestion of reports being sent at the same time,
   each base station will initiate a random delay timer.  Only when the
   timer expires will the base station send its report.





Imielinski & Navas            Experimental                     [Page 17]

RFC 2009            GPS-Based Addressing and Routing       November 1996


   For every base station that responds, the router will create an IP
   tunnel between it and the base station.  This tunnel will carry the
   GPScast packet traffic between the base station and the router.  Each
   responding base station and its geographic area of service will also
   be included in the router's geometric routing table as a possible
   destination for GPScast packets.  Any base station that does not
   respond for ten continuous Service Area Queries will be considered
   unreachable and will be dropped from the routing table.

3c-iv.         Hierarchical Router Structure and Multicast Groups

                       R5----------------------R6
                    /      \                /     \
                  R1---------R2           R3---------R4
                / | \      / | \        / | \      / | \
               b1 b2 b3   b4 b5 b6     b7 b8 b9 b10 b11 b12

   Figure 3: Two peer routers (R5 and R6) cooperatively servicing four
                   child routers (R1 - R4).

   For scalability purposes, a hierarchy of routers is used to transport
   messages from a sender to a receiver.  Each layer of peer routers
   would have its own multicast group address for the exchange of
   Service Area Queries and Reports between the peer routers.  However,
   routers in distinct subtrees need not know about the routers in other
   subtrees.  Therefore, multicast group addresses will also differ
   between hierarchy subtrees.  See figure 3.  For instance, routers R1
   and R2 would share a multicast group and would know about each other.
   At the same time, routers R3 and R4 would share a different multicast
   group and would know about each other.  However, routers R1 and R2
   would not know about R3 and R4, and vice versa.

   But how will the router know the location and number of its peer
   routers and who its parent router is?  As mentioned before, the
   router consults its configuration file upon start-up.  Included in
   this configuration file will be the the address of its parent router
   and the multicast group address that the peer routers will use.  This
   peer multicast group address will be used in the same manner as the
   base station multicast group address.  It will be used to send and
   receive Service Area Queries and Reports between the parent router
   and the peer routers.  There is only one difference.  When a router
   sends a Service Area Report, in addition to reporting its
   geographical service area, a router will include the multicast
   address of its children base stations.  The reason for this is
   explained in the router-failure recovery scheme described below.






Imielinski & Navas            Experimental                     [Page 18]

RFC 2009            GPS-Based Addressing and Routing       November 1996


3c-v.          Routing Optimizations

   The optimization described here attempts to reduce the latency of a
   GPScast.  It does so by reducing the the number of hops a packet must
   traverse before finding its destination.  The intuition behind the
   idea is this:  instead of going to the parent router and then to the
   sibling, simply go to the sibling directly.  As an additional
   benefit, this method prevents the parent router from becoming a
   bottleneck or a point of failure in the routing scheme.

   In this optimization, when a router attempts to determine who will
   receive the GPS packet, it considers its peer routers as if they were
   also its children in the routing hierarchy.  This means that the
   router will consider its service area to be the union of the service
   areas of its children and its peer routers.  Also, when the
   destination polygon intersects the router's service area polygon, the
   router will forward a copy of the GPScast packet to any child or peer
   router whose geographic service area contains or touches the packet's
   GPS destination polygon.

   However, before it sends a copy of the packet to a peer router, it
   first finds the polygon:

                               P = D /\ S

   where D stands for the packet's destination GPS polygon, S is the
   polygon representing the service area of the peer router, and P is
   the polygon that represents the intersection of D and S.  The polygon
   P is substituted for the destination polygon D in the packet and only
   then is the packet forwarded to the peer router.  This is necessary
   because the peer router will be using that same routing algorithm.
   Therefore, if the peer router receives a packet with the original
   destination polygon D, it will also route copies of the packet to all
   of its qualifying peer routers causing a chain of packet copies being
   bounced back and forth.

3c-vi.          Router-Failure Recovery Scheme

   In the case of a router failure, the system should be able to route
   around the failed router and continue to service GPScast messages.
   The responsibility of detecting whether a router has failed or not
   falls to the parent router.  Using Figure 3 as an example router
   hierarchy, the parent router R5 periodically sends out Service Area
   Query IGPSMP messages on its children's multicast group address.
   Thus, the child routers R1 and R2 will both receive this query.
   Normally, both routers will respond with a Service Area Report
   message.  This message contains a polygon describing their service
   areas and the multicast group address of their children.



Imielinski & Navas            Experimental                     [Page 19]

RFC 2009            GPS-Based Addressing and Routing       November 1996


   However, if a router, R1, does not respond to ten continuous queries,
   then it must be considered to have failed.  Upon detecting this, the
   parent router R5 will send a Set Service Area message to the child
   router, R2 telling it to assume responsibility for the base stations
   underneath the failed R1 router.  In this Set Service Area message,
   the parent router includes the multicast group address of R1's
   children.  The R2 router uses this multicast address to learn the
   service areas and IP addresses of R1's children.  The R2 router then
   issues a Service Area Report advertising its new enlarged service
   area responsibilities.  All peer and parent routers will then update
   their routing tables to include this new information.  When the
   failed router, R1, restarts, it will declare that it is alive and
   that it is again servicing its area.  All routers will then again
   update their routing tables.

   In the case that there is no parent router, such as at the top of the
   routing hierarchy, then each peer router will keep track of its
   neighbors.  If a neighbor router fails, then the first neighbor
   router to declare that it is taking over the base stations for the
   failed router will take responsibility.  The rest continues as
   before.

3c-vii.   Domain Name Service Issues

   Domain Name Servers (DNS) could be used to facilitate the use of GPS
   geographic addressing for sites of interest.  The aim is to describe
   specific geographic sites in a more natural and real-world manner
   using a postal-service like addressing method.  Essentially, the DNS
   would resolve a postal-service like address, such as
   City_Hall.New_York_City.New_York, into the IP address of the GPS
   router responsible for that site.  The GPS router would then route
   the message to all available recipients in the site.

   The DNS would be used when a message is sent using the

              site-code.city-code.state-code.country-code

   addressing scheme.  The DNS would evaluate the address in reverse
   starting with the country code, then the state code, etc.  This is
   the same method used currently by the IP DNS service to return IP
   addresses based on the country or geographic domains.










Imielinski & Navas            Experimental                     [Page 20]

RFC 2009            GPS-Based Addressing and Routing       November 1996


4.  Router Daemon and Host Library

4a. GPS Address Library - SendToGPS()

   A library for GPS address routing will be constructed.  The main
   routines contained in this library will be the SendToGPS() and
   RecvFromGPS() commands.  SendToGPS() has the following syntax:

   SendToGPS(int socket, GPS-Address *address, char *message, int size)

   where socket is a previously created datagram socket, address is a
   filled GPS-Address structure with the following form:
   typedef _GPS-Address {
           enum { point, circle, polygon } type;
           char *mail-address;
           struct
           {
                   enum { North, South, West, East } dir;
                   int hours, minutes, seconds;
           } *points;

   } GPS-Address;

   and message and size specify the actual message and its size.  The
   SendToGPS() routine will take the GPS-addressed message, encapsulate
   it in an IP packet, and then send it as a normal IP datagram.  The
   message is encapsulated in the following manner:

              --------------------------------------------------------
              |  IP Header with destination address set to 240.0.0.0 |
              --------------------------------------------------------
              |  Sender Identifier                                   |
              --------------------------------------------------------
              |  Address Type  - Circle|Polygon                      |
              --------------------------------------------------------
              |  Actual GPS Address (see below)                      |
              --------------------------------------------------------
              |  Body of Message                                     |
              --------------------------------------------------------

   where the Sender Identifier would consist of a combination of the
   sender's process id, host IP address, and the center of the
   destination polygon.  The Actual Address would be one of the
   following:

   circle  - single GPS address and range measured in centiminutes.





Imielinski & Navas            Experimental                     [Page 21]

RFC 2009            GPS-Based Addressing and Routing       November 1996


   polygon - list of GPS addresses terminated by the  impossible
                address: N 255 255 255.

   RecvFromGPS() has the following syntax:

   RecvFromGPS(int socket,GPS-Address *address,char *message,int size)

   where socket is a previously created datagram socket, address is an
   empty GPS-Address structure, and message and size specify message
   buffer and its size.

4b. Establishing A Default GPS Router

   The default GPS router is determined using the unicast routing table
   found in the UNIX kernel.  The local system administrator will have
   previously adjusted the table so that all GPScast messages are sent
   to the local GPS router.  However, if there is no route for GPScast
   messages in the table, then all messages will, by default, be sent to
   the default gateway.  If the default gateway does not support GPScast
   messages, then all attempts to send a GPScast will return an error.

   By default, all GPScast messages will initially have as their
   destination the class E address 240.0.0.0.  A route will be added to
   the kernel routing table by the system administrator for this
   address.  The route will specify the location of the local GPS
   router.  The "route" command will be used to affect the routing table
   and it can be placed in the /etc/rc.local or /etc/rc.ip files so that
   it will take effect each time the computer is booted.  For example,
   to specify that GPScast messages addressed to 240.0.0.0 should, by
   default, be sent to the router which resides on a computer on the
   same subnet with local address 128.6.5.53, use the following:

              /etc/route add host 240.0.0.0 128.6.5.53 0

   If the default destination for GPScast messages is a host that does
   not support GPS addressing, then Network Unreachable errors will be
   returned to any process attempting to route GPScasts through that
   host.

4c. GPSRouteD

   In order to provide the capability of GPS address routing throughout
   an IPv4-based internetwork, special-purpose routers will be created
   to support GPS address routing on top of the current Internet.  These
   routers, which will be called GPSRouteD, will use virtual point-to-
   point links called tunnels in order to connect two GPSRouteDs
   together over regular unicast networks.  The tunnels work by
   encapsulating the GPS address messages in IP datagrams and then



Imielinski & Navas            Experimental                     [Page 22]

RFC 2009            GPS-Based Addressing and Routing       November 1996


   transmitting the message to the host on the other end of the tunnel.
   In this manner, the GPS address messages look like normal unicast
   packets to all IPv4 routers in between the two GPS address routers.
   At the end of the tunnel, the receiving GPSRouteD removes the GPS
   address message from the datagram and continues the routing process.

   By using tunnels, the GPS routers can be established as a virtual
   internetwork throughout the current Internet without regard for the
   physical properties of the underlying networks.  Moreover, the use of
   tunnels means that the host on which the router daemon is running
   need not be connected to more than one subnet in order for the router
   to forward GPS messages.  This virtual internetwork would be
   responsible for routing GPS address messages only.  This virtual
   network, however, is not intended to be a permanent solution and is
   only intended to provide a means of supporting GPS address routing
   until it gains wider acceptance and support in the Internet
   infrastructure.

4c-i.   Configuration

   When a GPSRouteD initially executes, it first checks the file
   /etc/GPSRouteD.conf for configuration commands to add tunnel and
   multicast links to other GPS address routers.  There are two kinds of
   configuration commands:

           multicast  <multicast-address> <peer|child>

           tunnel  <local-addr> <remote-addr>
                   <parent|peer|child|host> <service-area>

   The tunnel command is used to create a tunnel between the local host
   on which the GPSRouteD executes and a remote host on which another
   GPSRouteD executes. The tunnel must be set up in the GPSRouteD.conf
   files at both ends before it will be used.

   The multicast command tells the router which multicast addresses to
   join.  These addresses will carry IGPSMP messages and replies.  The
   router will use these IGPSMP messages to build up and keep current
   its own internal routing table.

4d.     Multicast Address Resolution Protocol (MARP)

   Of course, this begs the question, how will the individual computers
   know which multicast addresses to join?  For example, an MH would
   have to join the multicast address of its current cell so that it can
   receive GPScast messages (using application-level filtering) or
   directions to join other multicast groups (using multicast
   filtering).  We have designed a protocol called Multicast Address



Imielinski & Navas            Experimental                     [Page 23]

RFC 2009            GPS-Based Addressing and Routing       November 1996


   Resolution Protocol (MARP) that works the same way as Reverse Address
   Resolution Protocol (RARP).  However, instead of returning the IP
   address of the MH, it will return multicast group address of the cell
   the MH is currently in.  The MH would then join this multicast group.

4e.     Internet GPS Management Protocol (IGPSMP)

   The Internet GPS Management Protocol (IGPSMP) is used by GPS routers
   to report, query, and inform their router counterparts about their
   geographical service areas.  The IGPSMP will also be used to verify
   that routers are correctly functioning.

   The vocabulary of IGPSMP will consist of six words:

   o       set service area - Used by the parent router to set the
             geographic service area of a router.  This is needed in
             order to automatically respond to router failure or new
             router boot-up.

   o       confirm service area - confirms that a router has received
             its service area.

   o       geographical service area query - This message will be used
             by a router to build up its geographical routing table.
             It is sent to all routers on the same level.


   o       service area report - This message is sent in response to a
            query request.  It contains a bounding closed polygon
            described using GPS coordinates which contains the service
            area for the router.

   o       ping - This message is sent periodically to ascertain whether
             the router is currently functioning properly.  Usually sent
             by the parent router in the hierarchy tree.

   o       alive signal - Usually sent as a reply to the ping message.
             Used by a router to indicate that it is functioning
             correctly.  It is also sent immediately after a router
             boots.

   All of IGPSMP messages will be sent on an all-routers multicast
   address for a particular hierarchy level.  The exact multicast
   address can be set in the router configuration file.

   Note that for the GPS-Multicast routing scheme, the time-to-live
   value of the service area reports will be varied in order to control
   the distribution of the information.  In GPS-Multicast routing, only



Imielinski & Navas            Experimental                     [Page 24]

RFC 2009            GPS-Based Addressing and Routing       November 1996


   the multicast group membership for very large partitions will be
   distributed throughout the country.  Smaller partition may only be
   distributed to neighbor routers.

5.      Working Without GPS Information

5a.     Users Without GPS Modules

   Mobile users without GPS modules can still participate - though at a
   very reduced level.  When an MH enters a cell, it can use an MARP to
   discover the local multicast group for that cell or atom.  As the
   user roams from cell to cell, the mobile host can keep track of the
   current cell that the user is in and adds or drops the multicast
   groups pertaining to those cells.  The user's GPS address can be set
   to be the center of the current cell.

5b.     Buildings block GPS radio frequencies.  What then?

   Each room can have a radio beacon placed on the ceiling.  The beacon
   will be weak enough so that it will not penetrate walls.  Each radio
   beacon will have its own GPS-address associated with it which it will
   broadcast.  When a mobile user enters a room, his MH will detect the
   beacon and read the beacon's GPS address.  The GPS-address of the MH
   will be set to the GPS-address of the beacon.  The MH will then use
   this beacon's GPS address in order to perform any message filtering
   that it needs to do.  Now the mobile user can have a GPS-address
   associated with him even though he is indoors and his GPS-module is
   useless.

6.      Application Layer Solution

   In this subsection we sketch a third solution which relies more
   heavily on the DNS.

   In the application layer solution the geographic information is added
   to the DNS which provides the full directory information down to the
   level of the IP address of each base station and its area of coverage
   represented as a polygon of coordinates.

   A new first level domain - "geographic" is added to the set of first
   level domains. The second level domain names include states, the
   third, counties and finally, the fourth: polygons  of coordinates, or
   so called points of interests. We can also allow, polygons to occur
   as elements of second, third domains to enable sending messages to
   larger areas.






Imielinski & Navas            Experimental                     [Page 25]

RFC 2009            GPS-Based Addressing and Routing       November 1996


   Thus a typical geographic address can look like

   city-hall-Palo-Alto.San-Mateo-County.California.geographic

   or

   Polygon.San-Mateo-County.California.geographic

   where Polygon is a sequence of coordinates.

   This geographic address is resolved in a similar way as the standard
   domain addresses are resolved today into a set of IP addresses of
   base stations which cover that geographic area. There are several
   possibilities here:

   a. A set of unicast messages is sent to all base stations
   corresponding to the IP addresses returned by the DNS. Each base
   station then forwards the message using either of the two last link
   solutions: application level or network level filtering.

   b. All the base stations join the temporary multicast group for the
   geographic area specified in the message. In this way we may avoid
   sending the same message across the same link several times. Thus,
   after the set of relevant base stations is determined by the DNS, the
   temporary multicast group is established and all packets with that
   multicast address are sent on that multicast address.

   c. Only one, central to the polygon base station is returned by the
   DNS just as in the IP unicast solution.  However that "central" base
   station will have to forward messages to the other base stations
   within the  polygon.

   Notice that we should distinguish between "small area" and "wide
   area" geographic mail. The "small area" mail will be most common  and
   will most likely involve just one base station, favoring a simple
   form of solution (a).

7.      Reliability

   Should the geographic messages be acknowledged?

   Since we have no control if  users are present in the target
   geographic area where the mail is distributed we do not see a need
   for individual acknowledgments from the message recipients.  However,
   we believe that the base stations (MSS) covering the target area of
   geographic mail should acknowledge the messages.





Imielinski & Navas            Experimental                     [Page 26]

RFC 2009            GPS-Based Addressing and Routing       November 1996


   Typically only a few base stations will be involved since typically
   we will not cover very broad geographic areas anyway.  We assume that
   the base stations, additionally to forwarding the the messages on
   their wireless interfaces will buffer them, either to periodically
   multicast them (emergency response) or to provide them to users who
   just entered a cell and download the "emergency stack" of messages
   for that area as a part of the service hand-off protocol.

8.      Security Considerations

   Some method of determining who has permission to send messages to a
   large geographical area is needed.  For instance, perhaps only the
   mayor of New York City has permission to send a message to all of New
   York City.

9.      References

   Deering, S., "Host Extensions for IP Multicasting", STD 5, RFC 1112,
   August 1989.

   S. Deering. Multicast Routing in a Datagram Internetwork. Ph.D.
   Thesis, Stanford University, (December 1991).

   J. O'Rourke, C.B. Chien, T. Olson, and D. Naddor, A new linear
   algorithm for intersecting convex polygons, Computer Graphics and
   Image Processing  19, 384-391 (1982).

   J. Ioannidis, D. Duchamp, and G. Q. Maquire. IP-Based Protocols for
   Mobile Internetworking. Proc. of ACM SIGCOMM Symposium on
   Communication, Architectures and Protocols, pages 235-245,
   (September, 1991).

10.      Authors' Addresses

      Tomasz Imielinski and Julio C. Navas
      Computer Science Department
      Busch Campus
      Rutgers, The State University
      Piscataway, NJ
      08855

      Phone:  908-445-3551
      EMail:  {imielins,navas}@cs.rutgers.edu








Imielinski & Navas            Experimental                     [Page 27]