开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > Windows编程 > 通讯编程 > 查看源码
models.ps
资源名称：ns-allinone-2.33.tar.gz　[点击查看]
上传用户：rrhhcc
上传日期：2015-12-11
资源大小：54129k
文件大小：131k
源码类别：

通讯编程

开发平台：

Visual C++

models.ps：源码内容
  1. none SetP %I p n
  2. %I t
  3. [ 0.5 -0 -0 0.5 79.5 460.5 ] concat
  4. %I
  5. 218 273 170 223 Line
  6. %I 2
  7. End
  9. Begin %I Line
  10. %I b 65535
  11. 1 0 0 [] 0 SetB
  12. %I cfg Black
  13. 0 0 0 SetCFg
  14. %I cbg White
  15. 1 1 1 SetCBg
  16. none SetP %I p n
  17. %I t
  18. [ 0.5 -0 -0 0.5 79.5 460.5 ] concat
  19. %I
  20. 170 224 266 173 Line
  21. %I 2
  22. End
  24. Begin %I Elli
  25. %I b 61680
  26. 1 0 0 [4 4 4 4] 0 SetB
  27. %I cfg Black
  28. 0 0 0 SetCFg
  29. %I cbg White
  30. 1 1 1 SetCBg
  31. %I p
  32. 1 SetP
  33. %I t
  34. [ 1 -0 -0 1 104 551 ] concat
  35. %I
  36. 156 165 20 20 Elli
  37. End
  39. Begin %I Elli
  40. %I b 61680
  41. 1 0 0 [4 4 4 4] 0 SetB
  42. %I cfg Black
  43. 0 0 0 SetCFg
  44. %I cbg White
  45. 1 1 1 SetCBg
  46. %I p
  47. 1 SetP
  48. %I t
  49. [ 1 -0 -0 1 248 479 ] concat
  50. %I
  51. 156 165 20 20 Elli
  52. End
  54. End %I eop
  56. showpage
  59. end
  60. %%EndDocument
  62.  endTexFig
  63.  551 1339 a Fj(Figure)15 b(1:)20 b(N-Lev)o(el)c(Hierarc)o(hical)h(La)o
  64. (y)o(out)30 1476 y(graph,)h(most)f(\top-lev)o(el")i(edges)f((i.e.)28
  65. b(one)18 b(that)f(w)o(as)h(part)f(of)g(the)i(original)g(graph))e(are)h
  66. (t)o(ypically)30 1533 y(longer)h(than)f(the)g(second-lev)o(el)i(edges,)
  67. f(while)h(the)e(second-lev)o(el)i(edges)f(are)f(t)o(ypically)i(longer)e
  68. (than)30 1589 y(third-lev)o(el)f(edges.)j(Figure)c(1)f(depicts)h(the)f
  69. (la)o(y)o(out)g(of)g(a)g(pure)g(hierarc)o(hical)i(graph.)101
  70. 1646 y(In)c(the)g(hierarc)o(hical)i(mo)q(dels,)e(it)g(is)h(p)q(ossible)
  71. g(to)f(de14ne)g(a)g(routing)g(p)q(olicy)h(based)f(on)g(the)g
  72. (principle)30 1702 y(that)f(routes)f(b)q(et)o(w)o(een)i(no)q(des)g
  73. (within)h(the)e(same)g(domain)h(should)g(sta)o(y)e(en)o(tirely)j
  74. (within)f(that)f(domain.)30 1758 y(W)l(e)e(augmen)o(t)g(the)h(edges)f
  75. (with)h(a)f(routing)h(p)q(olicy)h(w)o(eigh)o(t,)e(in)i(addition)f(to)f
  76. (the)g(Euclidean)j(edge)e(length,)30 1815 y(to)k(use)h(in)h
  77. (constructing)f(p)q(olicy-based)i(shortest)c(paths.)22
  78. b(Because)16 b(of)f(the)h(w)o(a)o(y)f(\domains")g(are)h(laid)30
  79. 1871 y(out)h(in)i(this)f(metho)q(d,)g(there)g(is)g(a)g(close)g
  80. (relationship)h(b)q(et)o(w)o(een)f(the)g(p)q(olicy)i(w)o(eigh)o(ts)d
  81. (and)h(the)g(edge)30 1928 y(lengths.)30 2048 y Fc(T)l(ransit-Stub)30
  82. 2134 y Fj(Our)23 b(T)l(ransit-Stub)g(mo)q(del)g(pro)q(duces)g(hierarc)o
  83. (hical)h(graphs)e(in)h(a)f(di13eren)o(t)g(w)o(a)o(y)l(,)h(b)o(y)f
  84. (comp)q(osing)30 2190 y(in)o(terconnected)d(transit)e(and)h(stub)g
  85. (domains.)28 b((See)18 b(Figure)f(2.))27 b(W)l(e)18
  86. b(14rst)f(construct)h(a)f(connected)30 2247 y(random)h(graph)f
  87. ((using)i(an)o(y)e(one)h(of)g(the)g(metho)q(ds)g(discussed)i
  88. (earlier);)f(eac)o(h)f(no)q(de)h(in)g(that)e(graph)30
  89. 2303 y(represen)o(ts)g(an)f(en)o(tire)h(transit)f(domain.)25
  90. b(Eac)o(h)16 b(no)q(de)h(in)h(that)e(graph)g(is)h(then)g(replaced)h(b)o
  91. (y)e(another)30 2359 y(connected)f(random)e(graph,)h(represen)o(ting)g
  92. (the)g(bac)o(kb)q(one)h(top)q(ology)e(of)h(one)g(transit)g(domain.)19
  93. b(Next,)30 2416 y(for)d(eac)o(h)i(no)q(de)f(in)h(eac)o(h)g(transit)e
  94. (domain,)i(w)o(e)f(generate)g(a)f(n)o(um)o(b)q(er)i(of)f(connected)h
  95. (random)e(graphs)30 2472 y(represen)o(ting)21 b(the)g(stub)g(domains)f
  96. (attac)o(hed)g(to)g(that)g(no)q(de.)37 b(Finally)l(,)23
  97. b(w)o(e)d(add)h(some)f(n)o(um)o(b)q(er)h(of)30 2529 y(additional)e
  98. (edges)e(b)q(et)o(w)o(een)h(pairs)f(of)g(no)q(des,)h(one)g(from)e(a)h
  99. (transit)g(domain)h(and)f(one)h(from)e(a)h(stub,)30 2585
  100. y(or)g(one)h(from)f(eac)o(h)h(of)g(t)o(w)o(o)e(di13eren)o(t)i(stub)g
  101. (domains.)29 b(Clearly)l(,)19 b(if)f(the)g(random)f(graphs)h(generated)
  102. 30 2642 y(are)f(all)h(connected,)g(this)f(construction)g(results)h(in)f
  103. (a)g(connected)h(graph.)25 b(W)l(e)17 b(note)g(that)f(Doar)g(and)30
  104. 2698 y(Leslie)j(prop)q(osed)d(a)h(graph)f(mo)q(del)h(that)f(has)h(a)f
  105. (similar)i(hierarc)o(hical)g(structure)e(to)g(our)g(mo)q(del,)i(but)30
  106. 2755 y(is)e(more)e(limited)k(in)e(scop)q(e)f([1].)101
  107. 2811 y(The)g(size)h(of)f(the)g(graph)g((n)o(um)o(b)q(er)g(of)g(no)q
  108. (des))g(and)g(distribution)i(of)e(no)q(des)h(b)q(et)o(w)o(een)f
  109. (transit)g(and)919 2940 y(3)p eop
  110. %%Page: 4 4
  111. 4 3 bop 195 266 a
  112.  23207797 11840716 0 0 39205928 19931873 startTexFig
  113.  195 266 a
  114. %%BeginDocument: domainstruct.eps
  115. %Magnification: 1.00
  116. /MyAppDict 100 dict dup begin def
  117. /$F2psDict 200 dict def
  118. $F2psDict begin
  119. $F2psDict /mtrx matrix put
  120. /col-1 {0 setgray} bind def
  121. /col0 {0.000 0.000 0.000 srgb} bind def
  122. /col1 {0.000 0.000 1.000 srgb} bind def
  123. /col2 {0.000 1.000 0.000 srgb} bind def
  124. /col3 {0.000 1.000 1.000 srgb} bind def
  125. /col4 {1.000 0.000 0.000 srgb} bind def
  126. /col5 {1.000 0.000 1.000 srgb} bind def
  127. /col6 {1.000 1.000 0.000 srgb} bind def
  128. /col7 {1.000 1.000 1.000 srgb} bind def
  129. /col8 {0.000 0.000 0.560 srgb} bind def
  130. /col9 {0.000 0.000 0.690 srgb} bind def
  131. /col10 {0.000 0.000 0.820 srgb} bind def
  132. /col11 {0.530 0.810 1.000 srgb} bind def
  133. /col12 {0.000 0.560 0.000 srgb} bind def
  134. /col13 {0.000 0.690 0.000 srgb} bind def
  135. /col14 {0.000 0.820 0.000 srgb} bind def
  136. /col15 {0.000 0.560 0.560 srgb} bind def
  137. /col16 {0.000 0.690 0.690 srgb} bind def
  138. /col17 {0.000 0.820 0.820 srgb} bind def
  139. /col18 {0.560 0.000 0.000 srgb} bind def
  140. /col19 {0.690 0.000 0.000 srgb} bind def
  141. /col20 {0.820 0.000 0.000 srgb} bind def
  142. /col21 {0.560 0.000 0.560 srgb} bind def
  143. /col22 {0.690 0.000 0.690 srgb} bind def
  144. /col23 {0.820 0.000 0.820 srgb} bind def
  145. /col24 {0.500 0.190 0.000 srgb} bind def
  146. /col25 {0.630 0.250 0.000 srgb} bind def
  147. /col26 {0.750 0.380 0.000 srgb} bind def
  148. /col27 {1.000 0.500 0.500 srgb} bind def
  149. /col28 {1.000 0.630 0.630 srgb} bind def
  150. /col29 {1.000 0.750 0.750 srgb} bind def
  151. /col30 {1.000 0.880 0.880 srgb} bind def
  152. /col31 {1.000 0.840 0.000 srgb} bind def
  154. end
  155. save
  156. -17.0 349.0 translate
  157. 1 -1 scale
  158. .9 .9 scale % to make patterns same scale as in xfig
  160. % This junk string is used by the show operators
  161. /PATsstr 1 string def
  162. /PATawidthshow {  % cx cy cchar rx ry string
  163.   % Loop over each character in the string
  164.   {  % cx cy cchar rx ry char
  165.     % Show the character
  166.     dup % cx cy cchar rx ry char char
  167.     PATsstr dup 0 4 -1 roll put % cx cy cchar rx ry char (char)
  168.     false charpath % cx cy cchar rx ry char
  169.     /clip load PATdraw
  170.     % Move past the character (charpath modified the
  171.     % current point)
  172.     currentpoint % cx cy cchar rx ry char x y
  173.     newpath
  174.     moveto % cx cy cchar rx ry char
  175.     % Reposition by cx,cy if the character in the string is cchar
  176.     3 index eq { % cx cy cchar rx ry
  177.       4 index 4 index rmoveto
  178.     } if
  179.     % Reposition all characters by rx ry
  180.     2 copy rmoveto % cx cy cchar rx ry
  181.   } forall
  182.   pop pop pop pop pop % -
  183.   currentpoint
  184.   newpath
  185.   moveto
  186. } bind def
  187. /PATcg {
  188.   7 dict dup begin
  189.     /lw currentlinewidth def
  190.     /lc currentlinecap def
  191.     /lj currentlinejoin def
  192.     /ml currentmiterlimit def
  193.     /ds [ currentdash ] def
  194.     /cc [ currentrgbcolor ] def
  195.     /cm matrix currentmatrix def
  196.   end
  197. } bind def
  198. % PATdraw - calculates the boundaries of the object and
  199. % fills it with the current pattern
  200. /PATdraw { % proc
  201.   save exch
  202.     PATpcalc % proc nw nh px py
  203.     5 -1 roll exec % nw nh px py
  204.     newpath
  205.     PATfill % -
  206.   restore
  207. } bind def
  208. % PATfill - performs the tiling for the shape
  209. /PATfill { % nw nh px py PATfill -
  210.   PATDict /CurrentPattern get dup begin
  211.     setfont
  212.     % Set the coordinate system to Pattern Space
  213.     PatternGState PATsg
  214.     % Set the color for uncolored pattezns
  215.     PaintType 2 eq { PATDict /PColor get PATsc } if
  216.     % Create the string for showing
  217.     3 index string % nw nh px py str
  218.     % Loop for each of the pattern sources
  219.     0 1 Multi 1 sub { % nw nh px py str source
  220. % Move to the starting location
  221. 3 index 3 index % nw nh px py str source px py
  222. moveto % nw nh px py str source
  223. % For multiple sources, set the appropriate color
  224. Multi 1 ne { dup PC exch get PATsc } if
  225. % Set the appropriate string for the source
  226. 0 1 7 index 1 sub { 2 index exch 2 index put } for pop
  227. % Loop over the number of vertical cells
  228. 3 index  % nw nh px py str nh
  229. { % nw nh px py str
  230.   currentpoint % nw nh px py str cx cy
  231.   2 index show % nw nh px py str cx cy
  232.   YStep add moveto % nw nh px py str
  233. } repeat % nw nh px py str
  234.     } for
  235.     5 { pop } repeat
  236.   end
  237. } bind def
  239. % PATkshow - kshow with the current pattezn
  240. /PATkshow { % proc string
  241.   exch bind % string proc
  242.   1 index 0 get % string proc char
  243.   % Loop over all but the last character in the string
  244.   0 1 4 index length 2 sub {
  245. % string proc char idx
  246.     % Find the n+1th character in the string
  247.     3 index exch 1 add get % string proe char char+1
  248.     exch 2 copy % strinq proc char+1 char char+1 char
  249.     % Now show the nth character
  250.     PATsstr dup 0 4 -1 roll put % string proc chr+1 chr chr+1 (chr)
  251.     false charpath % string proc char+1 char char+1
  252.     /clip load PATdraw
  253.     % Move past the character (charpath modified the current point)
  254.     currentpoint newpath moveto
  255.     % Execute the user proc (should consume char and char+1)
  256.     mark 3 1 roll % string proc char+1 mark char char+1
  257.     4 index exec % string proc char+1 mark...
  258.     cleartomark % string proc char+1
  259.   } for
  260.   % Now display the last character
  261.   PATsstr dup 0 4 -1 roll put % string proc (char+1)
  262.   false charpath % string proc
  263.   /clip load PATdraw
  264.   neewath
  265.   pop pop % -
  266. } bind def
  267. % PATmp - the makepattern equivalent
  268. /PATmp { % patdict patmtx PATmp patinstance
  269.   exch dup length 7 add % We will add 6 new entries plus 1 FID
  270.   dict copy % Create a new dictionary
  271.   begin
  272.     % Matrix to install when painting the pattern
  273.     TilingType PATtcalc
  274.     /PatternGState PATcg def
  275.     PatternGState /cm 3 -1 roll put
  276.     % Check for multi pattern sources (Level 1 fast color patterns)
  277.     currentdict /Multi known not { /Multi 1 def } if
  278.     % Font dictionary definitions
  279.     /FontType 3 def
  280.     % Create a dummy encoding vector
  281.     /Encoding 256 array def
  282.     3 string 0 1 255 {
  283.       Encoding exch dup 3 index cvs cvn put } for pop
  284.     /FontMatrix matrix def
  285.     /FontBBox BBox def
  286.     /BuildChar {
  287. mark 3 1 roll % mark dict char
  288. exch begin
  289. Multi 1 ne {PaintData exch get}{pop} ifelse  % mark [paintdata]
  290.   PaintType 2 eq Multi 1 ne or
  291.   { XStep 0 FontBBox aload pop setcachedevice }
  292.   { XStep 0 setcharwidth } ifelse
  293.   currentdict % mark [paintdata] dict
  294.   /PaintProc load % mark [paintdata] dict paintproc
  295. end
  296. gsave
  297.   false PATredef exec true PATredef
  298. grestore
  299. cleartomark % -
  300.     } bind def
  301.     currentdict
  302.   end % newdict
  303.   /foo exch % /foo newlict
  304.   definefont % newfont
  305. } bind def
  306. % PATpcalc - calculates the starting point and width/height
  307. % of the tile fill for the shape
  308. /PATpcalc { % - PATpcalc nw nh px py
  309.   PATDict /CurrentPattern get begin
  310.     gsave
  311. % Set up the coordinate system to Pattern Space
  312. % and lock down pattern
  313. PatternGState /cm get setmatrix
  314. BBox aload pop pop pop translate
  315. % Determine the bounding box of the shape
  316. pathbbox % llx lly urx ury
  317.     grestore
  318.     % Determine (nw, nh) the # of cells to paint width and height
  319.     PatHeight div ceiling % llx lly urx qh
  320.     4 1 roll % qh llx lly urx
  321.     PatWidth div ceiling % qh llx lly qw
  322.     4 1 roll % qw qh llx lly
  323.     PatHeight div floor % qw qh llx ph
  324.     4 1 roll % ph qw qh llx
  325.     PatWidth div floor % ph qw qh pw
  326.     4 1 roll % pw ph qw qh
  327.     2 index sub cvi abs % pw ph qs qh-ph
  328.     exch 3 index sub cvi abs exch % pw ph nw=qw-pw nh=qh-ph
  329.     % Determine the starting point of the pattern fill
  330.     %(px, py)
  331.     4 2 roll % nw nh pw ph
  332.     PatHeight mul % nw nh pw py
  333.     exch % nw nh py pw
  334.     PatWidth mul exch % nw nh px py
  335.   end
  336. } bind def
  338. % Save the original routines so that we can use them later on
  339. /oldfill /fill load def
  340. /oldeofill /eofill load def
  341. /oldstroke /stroke load def
  342. /oldshow /show load def
  343. /oldashow /ashow load def
  344. /oldwidthshow /widthshow load def
  345. /oldawidthshow /awidthshow load def
  346. /oldkshow /kshow load def
  348. % These defs are necessary so that subsequent procs don't bind in
  349. % the originals
  350. /fill    { oldfill } bind def
  351. /eofill    { oldeofill } bind def
  352. /stroke    { oldstroke } bind def
  353. /show    { oldshow } bind def
  354. /ashow    { oldashow } bind def
  355. /widthshow { oldwidthshow } bind def
  356. /awidthshow { oldawidthshow } bind def
  357. /kshow     { oldkshow } bind def
  358. /PATredef {
  359.   MyAppDict begin
  360.     {
  361.     /fill { /clip load PATdraw newpath } bind def
  362.     /eofill { /eoclip load PATdraw newpath } bind def
  363.     /stroke { PATstroke } bind def
  364.     /show { 0 0 null 0 0 6 -1 roll PATawidthshow } bind def
  365.     /ashow { 0 0 null 6 3 roll PATawidthshow }
  366.     bind def
  367.     /widthshow { 0 0 3 -1 roll PATawidthshow }
  368.     bind def
  369.     /awidthshow { PATawidthshow } bind def
  370.     /kshow { PATkshow } bind def
  371.   } {
  372.     /fill   { oldfill } bind def
  373.     /eofill { oldeofill } bind def
  374.     /stroke { oldstroke } bind def
  375.     /show   { oldshow } bind def
  376.     /ashow  { oldashow } bind def
  377.     /widthshow { oldwidthshow } bind def
  378.     /awidthshow { oldawidthshow } bind def
  379.     /kshow  { oldkshow } bind def
  380.     } ifelse
  381.   end
  382. } bind def
  383. false PATredef
  384. % Conditionally define setcmykcolor if not available
  385. /setcmykcolor where { pop } {
  386.   /setcmykcolor {
  387.     1 sub 4 1 roll
  388.     3 {
  389. 3 index add neg dup 0 lt { pop 0 } if 3 1 roll
  390.     } repeat
  391.     setrgbcolor - pop
  392.   } bind def
  393. } ifelse
  394. /PATsc { % colorarray
  395.   aload length % c1 ... cn length
  396.     dup 1 eq { pop setgray } { 3 eq { setrgbcolor } { setcmykcolor
  397.   } ifelse } ifelse
  398. } bind def
  399. /PATsg { % dict
  400.   begin
  401.     lw setlinewidth
  402.     lc setlinecap
  403.     lj setlinejoin
  404.     ml setmiterlimit
  405.     ds aload pop setdash
  406.     cc aload pop setrgbcolor
  407.     cm setmatrix
  408.   end
  409. } bind def
  411. /PATDict 3 dict def
  412. /PATsp {
  413.   true PATredef
  414.   PATDict begin
  415.     /CurrentPattern exch def
  416.     % If it's an uncolored pattern, save the color
  417.     CurrentPattern /PaintType get 2 eq {
  418.       /PColor exch def
  419.     } if
  420.     /CColor [ currentrgbcolor ] def
  421.   end
  422. } bind def
  423. % PATstroke - stroke with the current pattern
  424. /PATstroke {
  425.   countdictstack
  426.   save
  427.   mark
  428.   {
  429.     currentpoint strokepath moveto
  430.     PATpcalc % proc nw nh px py
  431.     clip newpath PATfill
  432.     } stopped {
  433. (*** PATstroke Warning: Path is too complex, stroking
  434.   with gray) =
  435.     cleartomark
  436.     restore
  437.     countdictstack exch sub dup 0 gt
  438. { { end } repeat } { pop } ifelse
  439.     gsave 0.5 setgray oldstroke grestore
  440.   } { pop restore pop } ifelse
  441.   newpath
  442. } bind def
  443. /PATtcalc { % modmtx tilingtype PATtcalc tilematrix
  444.   % Note: tiling types 2 and 3 are not supported
  445.   gsave
  446.     exch concat % tilingtype
  447.     matrix currentmatrix exch % cmtx tilingtype
  448.     % Tiling type 1 and 3: constant spacing
  449.     2 ne {
  450. % Distort the pattern so that it occupies
  451. % an integral number of device pixels
  452. dup 4 get exch dup 5 get exch % tx ty cmtx
  453. XStep 0 dtransform
  454. round exch round exch % tx ty cmtx dx.x dx.y
  455. XStep div exch XStep div exch % tx ty cmtx a b
  456. 0 YStep dtransform
  457. round exch round exch % tx ty cmtx a b dy.x dy.y
  458. YStep div exch YStep div exch % tx ty cmtx a b c d
  459. 7 -3 roll astore % { a b c d tx ty }
  460.     } if
  461.   grestore
  462. } bind def
  463. /PATusp {
  464.   false PATredef
  465.   PATDict begin
  466.     CColor PATsc
  467.   end
  468. } bind def
  470. % this is the pattern fill program from the Second edition Reference Manual
  471. % with changes to call the above pattern fill
  472. % left30
  473. 11 dict begin
  474. /PaintType 1 def
  475. /PatternType 1 def
  476. /TilingType 1 def
  477. /BBox [0 0 1 1] def
  478. /XStep 1 def
  479. /YStep 1 def
  480. /PatWidth 1 def
  481. /PatHeight 1 def
  482. /Multi 2 def
  483. /PaintData [
  484.   { clippath } bind
  485.   { 32 16 true [ 32 0 0 -16 0 16 ]
  486. {<c000c000300030000c000c000300030000c000c000300030
  487. 000c000c00030003c000c000300030000c000c0003000300
  488. 00c000c000300030000c000c00030003>}
  489.      imagemask } bind
  490. ] def
  491. /PaintProc {
  492. pop
  493. exec fill
  494. } def
  495. currentdict
  496. end
  497. /P1 exch def
  498. 1.1111 1.1111 scale %restore scale
  500. /cp {closepath} bind def
  501. /ef {eofill} bind def
  502. /gr {grestore} bind def
  503. /gs {gsave} bind def
  504. /sa {save} bind def
  505. /rs {restore} bind def
  506. /l {lineto} bind def
  507. /m {moveto} bind def
  508. /rm {rmoveto} bind def
  509. /n {newpath} bind def
  510. /s {stroke} bind def
  511. /sh {show} bind def
  512. /slc {setlinecap} bind def
  513. /slj {setlinejoin} bind def
  514. /slw {setlinewidth} bind def
  515. /srgb {setrgbcolor} bind def
  516. /rot {rotate} bind def
  517. /sc {scale} bind def
  518. /sd {setdash} bind def
  519. /ff {findfont} bind def
  520. /sf {setfont} bind def
  521. /scf {scalefont} bind def
  522. /sw {stringwidth} bind def
  523. /tr {translate} bind def
  524. /tnt {dup dup currentrgbcolor
  525.   4 -2 roll dup 1 exch sub 3 -1 roll mul add
  526.   4 -2 roll dup 1 exch sub 3 -1 roll mul add
  527.   4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb}
  528.   bind def
  529. /shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul
  530.   4 -2 roll mul srgb} bind def
  531.  /DrawEllipse {
  532. /endangle exch def
  533. /startangle exch def
  534. /yrad exch def
  535. /xrad exch def
  536. /y exch def
  537. /x exch def
  538. /savematrix mtrx currentmatrix def
  539. x y tr xrad yrad sc 0 0 1 startangle endangle arc
  540. closepath
  541. savematrix setmatrix
  542. } def
  544. /$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def
  545. /$F2psEnd {$F2psEnteredState restore end} def
  547. $F2psBegin
  548. 10 setmiterlimit
  549. n 0 792 m 0 0 l 612 0 l 612 792 l cp clip
  550.  0.06000 0.06000 sc
  551. 7.500 slw
  552. % Ellipse
  553. n 3075 3000 1500 675 0 360 DrawEllipse gs col-1 s gr
  555. % Ellipse
  556. n 2925 1275 600 225 0 360 DrawEllipse gs col-1 s gr
  558. % Ellipse
  559. n 975 1800 225 450 0 360 DrawEllipse gs col-1 s gr
  561. % Ellipse
  562. n 525 3525 225 375 0 360 DrawEllipse gs col-1 s gr
  564. % Ellipse
  565. n 2775 4500 375 225 0 360 DrawEllipse gs col-1 s gr
  567. % Ellipse
  568. n 5025 4650 739 739 0 360 DrawEllipse gs col-1 s gr
  570. % Ellipse
  571. n 5925 2175 480 480 0 360 DrawEllipse gs col-1 s gr
  573. % Ellipse
  574. n 8175 1800 600 225 0 360 DrawEllipse gs col-1 s gr
  576. % Ellipse
  577. n 9525 2475 450 225 0 360 DrawEllipse gs col-1 s gr
  579. % Ellipse
  580. n 9300 4350 525 225 0 360 DrawEllipse gs col-1 s gr
  582. % Ellipse
  583. n 9675 3450 525 225 0 360 DrawEllipse gs col-1 s gr
  585. % Ellipse
  586. n 3075 3000 1500 675 0 360 DrawEllipse gs 0.50 setgray ef gr gs col-1 s gr
  588. % Ellipse
  589. n 8100 3225 645 645 0 360 DrawEllipse gs 0.50 setgray ef gr gs col-1 s gr
  591. % Ellipse
  592. n 975 1950 75 75 0 360 DrawEllipse gs 0.50 setgray ef gr gs col-1 s gr
  594. % Ellipse
  595. n 2925 1275 75 75 0 360 DrawEllipse gs 0.50 setgray ef gr gs col-1 s gr
  597. % Ellipse
  598. n 525 3525 75 75 0 360 DrawEllipse gs 0.50 setgray ef gr gs col-1 s gr
  600. % Ellipse
  601. n 975 4800 75 75 0 360 DrawEllipse gs 0.50 setgray ef gr gs col-1 s gr
  603. % Ellipse
  604. n 2775 4425 75 75 0 360 DrawEllipse gs 0.50 setgray ef gr gs col-1 s gr
  606. % Ellipse
  607. n 4575 4350 75 75 0 360 DrawEllipse gs 0.50 setgray ef gr gs col-1 s gr
  609. % Ellipse
  610. n 5025 4200 75 75 0 360 DrawEllipse gs 0.50 setgray ef gr gs col-1 s gr
  612. % Ellipse
  613. n 5325 4725 75 75 0 360 DrawEllipse gs 0.50 setgray ef gr gs col-1 s gr
  615. % Ellipse
  616. n 4800 4875 75 75 0 360 DrawEllipse gs 0.50 setgray ef gr gs col-1 s gr
  618. % Ellipse
  619. n 5100 5175 75 75 0 360 DrawEllipse gs 0.50 setgray ef gr gs col-1 s gr
  621. % Ellipse
  622. n 5700 1950 75 75 0 360 DrawEllipse gs 0.50 setgray ef gr gs col-1 s gr
  624. % Ellipse
  625. n 6150 2025 75 75 0 360 DrawEllipse gs 0.50 setgray ef gr gs col-1 s gr
  627. % Ellipse
  628. n 5850 2325 75 75 0 360 DrawEllipse gs 0.50 setgray ef gr gs col-1 s gr
  630. % Ellipse
  631. n 7950 1800 75 75 0 360 DrawEllipse gs 0.50 setgray ef gr gs col-1 s gr
  633. % Ellipse
  634. n 9375 2475 75 75 0 360 DrawEllipse gs 0.50 setgray ef gr gs col-1 s gr
  636. % Ellipse
  637. n 9525 3450 75 75 0 360 DrawEllipse gs 0.50 setgray ef gr gs col-1 s gr
  639. % Ellipse
  640. n 9150 4275 75 75 0 360 DrawEllipse gs 0.50 setgray ef gr gs col-1 s gr
  642. % Ellipse
  643. n 2550 2625 75 75 0 360 DrawEllipse gs /PC [[0.00 0.00 0.00] [0.00 0.00 0.00]] def
  644. 15.00 15.00 sc P1 [16 0 0 -8 165.00 170.00]  PATmp PATsp ef gr PATusp gs col-1 s gr
  646. % Ellipse
  647. n 2025 3150 75 75 0 360 DrawEllipse gs /PC [[0.00 0.00 0.00] [0.00 0.00 0.00]] def
  648. 15.00 15.00 sc P1 [16 0 0 -8 130.00 205.00]  PATmp PATsp ef gr PATusp gs col-1 s gr
  650. % Ellipse
  651. n 2775 3450 75 75 0 360 DrawEllipse gs /PC [[0.00 0.00 0.00] [0.00 0.00 0.00]] def
  652. 15.00 15.00 sc P1 [16 0 0 -8 180.00 225.00]  PATmp PATsp ef gr PATusp gs col-1 s gr
  654. % Ellipse
  655. n 3600 3375 75 75 0 360 DrawEllipse gs /PC [[0.00 0.00 0.00] [0.00 0.00 0.00]] def
  656. 15.00 15.00 sc P1 [16 0 0 -8 235.00 220.00]  PATmp PATsp ef gr PATusp gs col-1 s gr
  658. % Ellipse
  659. n 3900 2700 75 75 0 360 DrawEllipse gs /PC [[0.00 0.00 0.00] [0.00 0.00 0.00]] def
  660. 15.00 15.00 sc P1 [16 0 0 -8 255.00 175.00]  PATmp PATsp ef gr PATusp gs col-1 s gr
  662. % Ellipse
  663. n 7875 2925 75 75 0 360 DrawEllipse gs /PC [[0.00 0.00 0.00] [0.00 0.00 0.00]] def
  664. 15.00 15.00 sc P1 [16 0 0 -8 520.00 190.00]  PATmp PATsp ef gr PATusp gs col-1 s gr
  666. % Ellipse
  667. n 8475 3075 75 75 0 360 DrawEllipse gs /PC [[0.00 0.00 0.00] [0.00 0.00 0.00]] def
  668. 15.00 15.00 sc P1 [16 0 0 -8 560.00 200.00]  PATmp PATsp ef gr PATusp gs col-1 s gr
  670. % Ellipse
  671. n 8100 3525 75 75 0 360 DrawEllipse gs /PC [[0.00 0.00 0.00] [0.00 0.00 0.00]] def
  672. 15.00 15.00 sc P1 [16 0 0 -8 535.00 230.00]  PATmp PATsp ef gr PATusp gs col-1 s gr
  674. % Ellipse
  675. n 5475 4350 75 75 0 360 DrawEllipse gs 0.50 setgray ef gr gs col-1 s gr
  677. % Ellipse
  678. n 1125 4800 450 225 0 360 DrawEllipse gs col-1 s gr
  680. % Polyline
  681. n 975 1875 m 1050 1575 l gs 0.50 setgray ef gr gs col-1 s gr 
  682. % Polyline
  683. n 900 1950 m 825 1650 l gs 0.50 setgray ef gr gs col-1 s gr 
  684. % Polyline
  685. n 3000 1275 m 3300 1275 l gs 0.50 setgray ef gr gs col-1 s gr 
  686. % Polyline
  687. n 2850 1275 m 2475 1275 l gs 0.50 setgray ef gr gs col-1 s gr 
  688. % Polyline
  689. n 525 3450 m 450 3300 l gs 0.50 setgray ef gr gs col-1 s gr 
  690. % Polyline
  691. n 525 3600 m 450 3750 l gs 0.50 setgray ef gr gs col-1 s gr 
  692. % Polyline
  693. n 1050 4800 m 1350 4800 l gs 0.50 setgray ef gr gs col-1 s gr 
  694. % Polyline
  695. n 975 4725 m 2775 3450 l gs 0.50 setgray ef gr gs col-1 s gr 
  696. % Polyline
  697. n 3525 3450 m 2775 4350 l gs 0.50 setgray ef gr gs col-1 s gr 
  698. % Polyline
  699. n 2625 2700 m 3525 3300 l gs 0.50 setgray ef gr gs col-1 s gr 
  700. % Polyline
  701. n 2625 2625 m 3825 2700 l gs 0.50 setgray ef gr gs col-1 s gr 
  702. % Polyline
  703. n 3900 2775 m 3675 3300 l gs 0.50 setgray ef gr gs col-1 s gr 
  704. % Polyline
  705. n 2100 3075 m 2550 2625 l gs 0.50 setgray ef gr gs col-1 s gr 
  706. % Polyline
  707. n 2100 3225 m 2775 3450 l gs 0.50 setgray ef gr gs col-1 s gr 
  708. % Polyline
  709. n 2850 3450 m 3525 3375 l gs 0.50 setgray ef gr gs col-1 s gr 
  710. % Polyline
  711. n 1050 2025 m 2025 3150 l gs 0.50 setgray ef gr gs col-1 s gr 
  712. % Polyline
  713. n 600 3525 m 2025 3150 l gs 0.50 setgray ef gr gs col-1 s gr 
  714. % Polyline
  715. n 2925 1350 m 2550 2625 l gs 0.50 setgray ef gr gs col-1 s gr 
  716. % Polyline
  717. n 3975 2700 m 5850 2325 l gs 0.50 setgray ef gr gs col-1 s gr 
  718. % Polyline
  719. n 5925 2325 m 6075 2100 l gs 0.50 setgray ef gr gs col-1 s gr 
  720. % Polyline
  721. n 6075 2025 m 5700 1950 l gs 0.50 setgray ef gr gs col-1 s gr 
  722. % Polyline
  723. n 5700 2025 m 5850 2250 l gs 0.50 setgray ef gr gs col-1 s gr 
  724. % Polyline
  725. n 8025 1800 m 8400 1800 l gs 0.50 setgray ef gr gs col-1 s gr 
  726. % Polyline
  727. n 7950 1875 m 7875 2850 l gs 0.50 setgray ef gr gs col-1 s gr 
  728. % Polyline
  729. n 7950 2925 m 8400 3075 l gs 0.50 setgray ef gr gs col-1 s gr 
  730. % Polyline
  731. n 8475 3150 m 8175 3525 l gs 0.50 setgray ef gr gs col-1 s gr 
  732. % Polyline
  733. n 8025 3450 m 7875 2925 l gs 0.50 setgray ef gr gs col-1 s gr 
  734. % Polyline
  735. n 9300 2475 m 8475 3075 l 8550 3000 l gs 0.50 setgray ef gr gs col-1 s gr 
  736. % Polyline
  737. n 9450 2475 m 9675 2400 l gs 0.50 setgray ef gr gs col-1 s gr 
  738. % Polyline
  739. n 9450 2475 m 9675 2625 l gs 0.50 setgray ef gr gs col-1 s gr 
  740. % Polyline
  741. n 9600 3375 m 9825 3300 l gs 0.50 setgray ef gr gs col-1 s gr 
  742. % Polyline
  743. n 9600 3450 m 9900 3525 l gs 0.50 setgray ef gr gs col-1 s gr 
  744. % Polyline
  745. n 9450 3450 m 8550 3075 l gs 0.50 setgray ef gr gs col-1 s gr 
  746. % Polyline
  747. n 8175 3525 m 9150 4275 l gs 0.50 setgray ef gr gs col-1 s gr 
  748. % Polyline
  749. n 9225 4275 m 9450 4275 l gs 0.50 setgray ef gr gs col-1 s gr 
  750. % Polyline
  751. n 5925 2400 m 7875 2925 l gs 0.50 setgray ef gr gs col-1 s gr 
  752. % Polyline
  753. n 3975 2775 m 8025 3525 l gs 0.50 setgray ef gr gs col-1 s gr 
  754. % Polyline
  755. n 3675 3450 m 4500 4275 l gs 0.50 setgray ef gr gs col-1 s gr 
  756. % Polyline
  757. n 4650 4350 m 5025 4200 l gs 0.50 setgray ef gr gs col-1 s gr 
  758. % Polyline
  759. n 5100 4275 m 5325 4725 l gs 0.50 setgray ef gr gs col-1 s gr 
  760. % Polyline
  761. n 5250 4725 m 4875 4875 l gs 0.50 setgray ef gr gs col-1 s gr 
  762. % Polyline
  763. n 4800 4800 m 5025 4275 l gs 0.50 setgray ef gr gs col-1 s gr 
  764. % Polyline
  765. n 4575 4425 m 4800 4875 l gs 0.50 setgray ef gr gs col-1 s gr 
  766. % Polyline
  767. n 4800 4950 m 5025 5175 l gs 0.50 setgray ef gr gs col-1 s gr 
  768. % Polyline
  769. n 5100 4200 m 5400 4350 l gs 0.50 setgray ef gr gs col-1 s gr 
  770. % Polyline
  771.  [66.7] 0 sd
  772. n 5550 4350 m 9075 4275 l gs 0.50 setgray ef gr gs col-1 s gr  [] 0 sd
  773. % Polyline
  774. gs  clippath
  775. 2620 4927 m 2690 4825 l 2676 4948 l 2733 4796 l 2677 4775 l  cp clip
  776. n 2475 5400 m 2700 4800 l gs 0.50 setgray ef gr gs col-1 s gr gr
  778. % arrowhead
  779. n 2620 4927 m 2690 4825 l 2676 4948 l  col-1 s
  780. % Polyline
  781. gs  clippath
  782. 4050 5027 m 4173 5030 l 4063 5086 l 4221 5051 l 4208 4992 l  cp clip
  783. n 2475 5400 m 4200 5025 l gs 0.50 setgray ef gr gs col-1 s gr gr
  785. % arrowhead
  786. n 4050 5027 m 4173 5030 l 4063 5086 l  col-1 s
  787. % Polyline
  788. gs  clippath
  789. 1771 5113 m 1674 5036 l 1796 5059 l 1649 4991 l 1624 5046 l  cp clip
  790. n 2475 5400 m 1650 5025 l gs 0.50 setgray ef gr gs col-1 s gr gr
  792. % arrowhead
  793. n 1771 5113 m 1674 5036 l 1796 5059 l  col-1 s
  794. % Polyline
  795. gs  clippath
  796. 7531 2407 m 7562 2526 l 7478 2435 l 7556 2578 l 7609 2549 l  cp clip
  797. n 5175 975 m 7125 1725 l 7575 2550 l gs col-1 s gr gr
  799. % arrowhead
  800. n 7531 2407 m 7562 2526 l 7478 2435 l  col-1 s
  801. % Polyline
  802. gs  clippath
  803. 6591 1749 m 6473 1785 l 6560 1698 l 6422 1782 l 6453 1833 l  cp clip
  804. n 7800 975 m 6450 1800 l gs col-1 s gr gr
  806. % arrowhead
  807. n 6591 1749 m 6473 1785 l 6560 1698 l  col-1 s
  808. % Polyline
  809. gs  clippath
  810. 7208 4550 m 7144 4444 l 7250 4508 l 7136 4393 l 7093 4436 l  cp clip
  811. n 7500 4800 m 7125 4425 l gs col-1 s gr gr
  813. % arrowhead
  814. n 7208 4550 m 7144 4444 l 7250 4508 l  col-1 s
  815. % Polyline
  816. gs  clippath
  817. 4235 2223 m 4140 2303 l 4187 2188 l 4092 2320 l 4141 2355 l  cp clip
  818. n 5100 975 m 4125 2325 l gs col-1 s gr gr
  820. % arrowhead
  821. n 4235 2223 m 4140 2303 l 4187 2188 l  col-1 s
  822. % Polyline
  823. n 2700 4425 m 2550 4500 l gs col-1 s gr 
  824. % Polyline
  825. n 2850 4425 m 3075 4575 l gs col-1 s gr 
  826. /Times-Roman ff 240.00 scf sf
  827. 2175 5775 m
  828. gs 1 -1 sc (Stub Domains) col-1 sh gr
  829. /Times-Roman ff 240.00 scf sf
  830. 6975 5025 m
  831. gs 1 -1 sc (Stub-Stub edge) col-1 sh gr
  832. /Times-Roman ff 240.00 scf sf
  833. 4575 900 m
  834. gs 1 -1 sc (Transit Domains) col-1 sh gr
  835. /Times-Roman ff 240.00 scf sf
  836. 7275 900 m
  837. gs 1 -1 sc (Multi-homed Stub) col-1 sh gr
  838. $F2psEnd
  839. rs
  840. end
  841. %%EndDocument
  843.  endTexFig
  844.  518 1114 a Fj(Figure)15 b(2:)20 b(T)l(ransit-Stub)c(Domain)f
  845. (Structure)30 1250 y(stub)g(domains)h(is)g(con)o(trolled)g(b)o(y)f(the)
  846. g(follo)o(wing)h(parameters:)337 1338 y Fc(P)o(arameter)274
  847. b(Meaning)i(Example)p 312 1356 1237 2 v 440 1396 a Fi(T)159
  848. b Fj(#)15 b(transit)g(domains)335 b(6)431 1452 y Fi(N)468
  849. 1459 y Fg(t)626 1452 y Fj((a)o(vg))14 b(no)q(des/transit)h(domain)152
  850. b(15)436 1509 y Fi(K)f Fj((a)o(vg))14 b(stub)h(domains/transit)g(no)q
  851. (de)51 b(12)429 1565 y Fi(N)466 1572 y Fg(s)626 1565
  852. y Fj((a)o(vg))14 b(no)q(des/stub)i(domain)197 b(8)p
  853. 312 1584 V 626 1623 a(total)15 b(no)q(des)478 b(8730)30
  854. 1712 y(As)15 b(the)g(table)h(sho)o(ws,)e(it)i(is)f(not)g(di16cult)i
  855. (to)d(generate)h(rather)g(large)g(graphs)g(with)h(this)f(metho)q(d.)101
  856. 1768 y(Note)h(that)g(the)h(parameters)f(giv)o(en)i(are)e(a)o(v)o
  857. (erages.)24 b(In)17 b(our)g(implemen)o(tation,)h(w)o(e)f(\randomize")
  858. 30 1824 y(the)e(n)o(um)o(b)q(ers)h(of)f(no)q(des)g(in)h(the)g(transit)e
  859. (domains)i(while)h(preserving)f(the)f(a)o(v)o(erage.)101
  860. 1881 y(The)d(v)m(alues)h(of)e Fi(K)k Fj(and)d Fi(N)547
  861. 1888 y Fg(s)576 1881 y Fj(for)f(eac)o(h)h(transit)g(no)q(de)g(and)g
  862. (stub)g(domain)g(are)g(similarly)h(randomized.)30 1937
  863. y(Our)22 b(implemen)o(tation)h(also)f(allo)o(ws)f(di13eren)o(t)h
  864. (random)f(graph)h(metho)q(ds)g(and)f(parameters)g(to)g(b)q(e)30
  865. 1994 y(plugged)16 b(in)g(to)f(construct)g(transit)f(and)i(stub)f
  866. (domain)h(subgraphs)f(with)h(di13eren)o(t)f(c)o(haracteristics.)101
  867. 2050 y(Once)20 b(the)g(complete)h(graph)e(is)h(constructed,)h(in)o
  868. (teger)f(edge)g(w)o(eigh)o(ts)g(are)f(assigned)i(in)f(suc)o(h)g(a)30
  869. 2107 y(w)o(a)o(y)13 b(that)g(the)h(follo)o(wing)g(routing)g(c)o
  870. (haracteristics)g(are)f(exhibited)j(when)f(the)e(edge)h(w)o(eigh)o(ts)g
  871. (are)f(used)30 2163 y(b)o(y)19 b(a)g(shortest)f(path)h(algorithm:)27
  872. b(The)19 b(routing)g(c)o(haracteristics)h(of)e(the)h(curren)o(t)g(In)o
  873. (ternet)g(can)g(b)q(e)30 2220 y(summarized)d(b)o(y)f(the)g(follo)o
  874. (wing)h(general)g(principles:)98 2312 y Fe(17)23 b
  875. Fj(The)12 b(path)g(connecting)i(t)o(w)o(o)c(no)q(des)j(in)g(the)g(same)
  876. f(domain)g(sta)o(ys)g(en)o(tirely)h(within)g(that)f(domain.)98
  877. 2405 y Fe(17)23 b Fj(The)c(shortest)f(path)h(connecting)h(no)q(de)g
  878. Fi(u)f Fj(in)h(stub)g(domain)f Fi(U)24 b Fj(to)19 b(no)q(de)g
  879. Fi(v)i Fj(in)f(another)f(stub)144 2461 y(domain)14 b
  880. Fi(V)24 b Fj(go)q(es)15 b(from)e Fi(U)20 b Fj(through)14
  881. b(one)g(or)g(more)g(transit)g(domains)h(to)f Fi(V)c Fj(,)k(and)g(do)q
  882. (es)h(not)f(pass)144 2518 y(through)g(an)o(y)h(other)g(stub)g(domains.)
  883. 98 2611 y Fe(17)23 b Fj(In)11 b(case)g(t)o(w)o(o)e(stub)i(domains)g
  884. (are)f(connected)i(directly)g(via)f(a)f(stub-stub)h(edge,)g(the)g(path)
  885. g(b)q(et)o(w)o(een)144 2667 y(t)o(w)o(o)i(no)q(des)j(on)f(the)g(t)o(w)o
  886. (o)e(domains)j Fb(may)j Fj((but)c(need)g(not))g(go)f(along)h(that)f
  887. (edge)h(and)h(a)o(v)o(oid)e(an)o(y)144 2724 y(transit)g(domains.)101
  888. 2816 y(The)h(edge)h(w)o(eigh)o(ts)e(to)h(b)q(e)h(calculated)g(and)g
  889. (assigned)g(are:)919 2940 y(4)p eop
  890. %%Page: 5 5
  891. 5 4 bop 426 305 a Fi(W)469 312 y Fg(tt)553 305 y Fj(W)l(eigh)o(t)16
  892. b(of)e(a)h(transit-transit)g(in)o(terdomain)h(edge)426
  893. 362 y Fi(W)469 369 y Fg(ts)553 362 y Fj(W)l(eigh)o(t)g(of)e(a)h
  894. (transit-stub)g(in)o(terdomain)h(edge)426 418 y Fi(W)469
  895. 425 y Fg(ss)553 418 y Fj(W)l(eigh)o(t)g(of)e(a)h(stub-stub)h(in)o
  896. (terdomain)g(edge)30 508 y(Note)d(that)g(all)h(edges)f(of)g(the)h(same)
  897. f(t)o(yp)q(e)g(are)g(giv)o(en)h(the)f(same)g(w)o(eigh)o(t.)19
  898. b(Also,)14 b(all)g Fb(intr)n(a)p Fj(domain)g(edges)30
  899. 565 y(are)k(giv)o(en)i(unit)f(edge)g(w)o(eigh)o(t.)30
  900. b(By)19 b(making)g(the)g(w)o(eigh)o(ts)f(of)g(the)h Fb(inter)p
  901. Fj(domain)g(edges)g(su16cien)o(tly)30 621 y(large,)d(w)o(e)g(guaran)o
  902. (tee)f(that)h(the)g(path)g(b)q(et)o(w)o(een)g(an)o(y)g(t)o(w)o(o)f(no)q
  903. (des)h(in)h(the)f(same)g(domain)h(will)h(remain)30 677
  904. y(within)e(that)f(domain.)101 734 y(In)e(calculating)i(the)e(w)o(eigh)o
  905. (ts)g(of)g(the)g(in)o(terdomain)h(edges,)f(the)g(follo)o(wing)h(quan)o
  906. (tities,)g(tak)o(en)f(from)30 790 y(the)i(constructed)h(graph,)e(are)h
  907. (used:)302 880 y Fc(P)o(arameter)433 b(Meaning)p 278
  908. 899 1305 2 v 377 938 a Fi(D)415 945 y Fa(top)592 938
  909. y Fj(Diameter)15 b(of)g(transit-domain)g(connectivit)o(y)i(graph)396
  910. 995 y Fi(D)434 1002 y Fg(t)592 995 y Fj(Maxim)o(um)e(diameter)h(of)e
  911. (an)o(y)h(transit)g(domain)h(graph)394 1051 y Fi(D)432
  912. 1058 y Fg(s)592 1051 y Fj(Maxim)o(um)f(diameter)h(of)e(an)o(y)h(stub)h
  913. (domain)f(graph)p 278 1070 V 101 1143 a(The)g(follo)o(wing)h(constrain)
  914. o(ts)f(guaran)o(tee)f(the)h(desired)i(lo)q(calit)o(y)f(c)o
  915. (haracteristics:)117 1233 y Fc(Constrain)o(t)676 b(Result)p
  916. 59 1251 1743 2 v 130 1291 a Fj(2)p Fi(W)196 1298 y Fg(ss)243
  917. 1291 y Fi(>)13 b(D)329 1298 y Fg(s)443 1291 y Fj(In)o(tra-stub)i
  918. (preferred)g(o)o(v)o(er)g(an)o(y)f(In)o(ter-stub)i(path)135
  919. 1347 y(2)p Fi(W)201 1354 y Fg(tt)241 1347 y Fi(>)d(D)327
  920. 1354 y Fg(t)443 1347 y Fj(In)o(tra-transit)h(preferred)i(o)o(v)o(er)e
  921. (an)o(y)h(In)o(ter-transit)g(path)84 1404 y(2)p Fi(W)150
  922. 1411 y Fg(ts)193 1404 y Fi(>)e(D)279 1411 y Fa(top)331
  923. 1404 y Fi(W)374 1411 y Fg(tt)412 1404 y Fj(+)d(()p Fi(D)513
  924. 1411 y Fa(top)575 1404 y Fj(+)h(1))p Fi(D)700 1411 y
  925. Fg(t)443 1460 y Fj(No)k(shortcut)f(via)i(a)f(stub)g(no)q(de)h
  926. (connected)g(to)f(an)o(y)f(pair)i(of)f(transit)g(no)q(des)84
  927. 1517 y(2)p Fi(W)150 1524 y Fg(ss)197 1517 y Fi(>)e Fj(2)p
  928. Fi(D)306 1524 y Fg(s)334 1517 y Fj(+)d(2)p Fi(W)445 1524
  929. y Fg(ts)486 1517 y Fj(+)g Fi(D)569 1524 y Fa(top)621
  930. 1517 y Fi(W)664 1524 y Fg(tt)702 1517 y Fj(+)h Fi(D)786
  931. 1524 y Fa(top)838 1517 y Fi(D)876 1524 y Fg(t)443 1573
  932. y Fj(Ev)o(ery)k(all-transit)g(path)h(preferred)f(o)o(v)o(er)f(an)o(y)h
  933. (path)g(with)h(three)f(stubs)84 1630 y Fi(W)127 1637
  934. y Fg(ss)174 1630 y Fe(31)e Fj(2)p Fi(W)288 1637 y Fg(ts)329
  935. 1630 y Fj(+)d Fi(17)51 b Fj(Direct)15 b(connection)h(b)q(et)o(w)o
  936. (een)g(2)f(stubs)g(ma)o(y)f(b)q(e)i(preferred)g(sometimes.)30
  937. 1720 y(By)f(assigning)h(the)g(follo)o(wing)f(v)m(alues,)h(the)g(ab)q(o)
  938. o(v)o(e)f(constrain)o(ts)f(are)h(satis14ed:)534 1822
  939. y Fi(W)577 1829 y Fg(tt)646 1822 y Fj(:=)41 b Fe(d)p
  940. Fi(D)793 1829 y Fg(t)808 1822 y Fi(=)p Fj(2)o Fe(e)530
  941. 1891 y Fi(W)573 1898 y Fg(ts)646 1891 y Fj(:=)g Fe(d)p
  942. Fi(D)793 1898 y Fa(top)845 1891 y Fi(W)888 1898 y Fg(tt)916
  943. 1891 y Fi(=)p Fj(2)o Fe(e)11 b Fj(+)f Fe(d)p Fj(()p
  944. Fi(D)1113 1898 y Fa(top)1175 1891 y Fj(+)g(1))p Fi(D)1299
  945. 1898 y Fg(t)1313 1891 y Fe(e)526 1960 y Fi(W)569 1967
  946. y Fg(ss)646 1960 y Fj(:=)41 b Fi(D)773 1967 y Fg(s)801
  947. 1960 y Fj(+)11 b(2)p Fi(W)913 1967 y Fg(ts)101 2062 y
  948. Fj(The)i(domains)h(in)g(transit-stub)f(graphs)g(are)g(placed)h(in)g
  949. (the)g(plane)g(in)g(suc)o(h)g(a)f(w)o(a)o(y)f(that)g(they)i(ma)o(y)30
  950. 2118 y(o)o(v)o(erlap)f(one)g(another.)19 b(The)14 b(same)e(scale)i(is)g
  951. (used)g(throughout)e(the)i(construction)f(pro)q(cess;)h(it)f(is)h(com-)
  952. 30 2175 y(puted)f(from)f(the)h(parameters)f(giv)o(en)h(to)f(the)h
  953. (graph)g(construction)g(routine.)19 b(The)13 b(pro)q(cess)g(is)g
  954. (depicted)30 2231 y(sc)o(hematically)h(in)f(Figure)f(3.)19
  955. b(A)12 b(top-lev)o(el)i(graph)e(determines)h(the)f(lo)q(cation)h(and)g
  956. (connectivit)o(y)g(of)f(the)30 2288 y(transit)j(domains;)g(that)f(is,)i
  957. (eac)o(h)f(no)q(de)h(of)f(the)g(top-lev)o(el)h(graph)f(corresp)q(onds)h
  958. (to)e(a)h(transit)g(domain.)30 2344 y(Eac)o(h)21 b(no)q(de)g(of)f(the)h
  959. (top-lev)o(el)h(graph)e(is)i(then)f(replaced)h(b)o(y)e(a)h(complete)g
  960. (transit)f(domain)i(graph,)30 2400 y(whose)d(scale)h((as)e(a)g
  961. (fraction)h(of)g(the)g(total)f(length)i(of)f(a)f(side)i(of)f(the)g
  962. (unit)h(square))e(is)i(determined)30 2457 y(b)o(y)c(the)h(parameter)e
  963. Fb(tr)n(ansfr)n(ac)h Fj(of)g(the)g(program.)22 b(Stub)17
  964. b(domains)g(are)f(created)g(with)h(a)f(scale)h(that)e(is)30
  965. 2513 y(some)e(fraction)h(of)f(the)h(global)g(scale;)h(this)f(fraction)g
  966. (is)g(again)g(a)f(program)g((compile-time))i(parameter)30
  967. 2570 y Fb(stubfr)n(ac)p Fj(.)k(Eac)o(h)14 b(stub)h(domain)f(is)h
  968. (placed)g(within)h(a)d(certain)i(distance)g(of)f(the)g(transit)g(no)q
  969. (de)h(to)e(whic)o(h)30 2626 y(it)h(is)g(attac)o(hed;)g(no)f(stub)h(no)q
  970. (de)g(is)h(more)e(than)h(the)g(scale)g(of)f(the)h(stub)g(domain)g(a)o
  971. (w)o(a)o(y)e(from)h(its)h(transit)30 2683 y(no)q(de.)20
  972. b(Th)o(us,)12 b(in)h(transit-stub)g(graphs,)f(p)q(olicy)i(and)f
  973. (length-based)g(edge)g(w)o(eigh)o(ts)f(of)g(paths)h(ma)o(y)e(ha)o(v)o
  974. (e)30 2739 y(little)17 b(to)d(do)h(with)h(eac)o(h)f(other.)919
  975. 2940 y(5)p eop
  976. %%Page: 6 6
  977. 6 5 bop 484 266 a
  978.  14077296 15787623 11182899 22497361 25260195 38284984 startTexFig
  979.  484 266 a
  980. %%BeginDocument: tslayfig.ps
  982. /arrowhead {
  983. 0 begin
  984. transform originalCTM itransform
  985. /taily exch def
  986. /tailx exch def
  987. transform originalCTM itransform
  988. /tipy exch def
  989. /tipx exch def
  990. /dy tipy taily sub def
  991. /dx tipx tailx sub def
  992. /angle dx 0 ne dy 0 ne or { dy dx atan } { 90 } ifelse def
  993. gsave
  994. originalCTM setmatrix
  995. tipx tipy translate
  996. angle rotate
  997. newpath
  998. arrowHeight neg arrowWidth 2 div moveto
  999. 0 0 lineto
  1000. arrowHeight neg arrowWidth 2 div neg lineto
  1001. patternNone not {
  1002. originalCTM setmatrix
  1003. /padtip arrowHeight 2 exp 0.25 arrowWidth 2 exp mul add sqrt brushWidth mul
  1004. arrowWidth div def
  1005. /padtail brushWidth 2 div def
  1006. tipx tipy translate
  1007. angle rotate
  1008. padtip 0 translate
  1009. arrowHeight padtip add padtail add arrowHeight div dup scale
  1010. arrowheadpath
  1011. ifill
  1012. } if
  1013. brushNone not {
  1014. originalCTM setmatrix
  1015. tipx tipy translate
  1016. angle rotate
  1017. arrowheadpath
  1018. istroke
  1019. } if
  1020. grestore
  1021. end
  1022. } dup 0 9 dict put def
  1024. /arrowheadpath {
  1025. newpath
  1026. arrowHeight neg arrowWidth 2 div moveto
  1027. 0 0 lineto
  1028. arrowHeight neg arrowWidth 2 div neg lineto
  1029. } def
  1031. /leftarrow {
  1032. 0 begin
  1033. y exch get /taily exch def
  1034. x exch get /tailx exch def
  1035. y exch get /tipy exch def
  1036. x exch get /tipx exch def
  1037. brushLeftArrow { tipx tipy tailx taily arrowhead } if
  1038. end
  1039. } dup 0 4 dict put def
  1041. /rightarrow {
  1042. 0 begin
  1043. y exch get /tipy exch def
  1044. x exch get /tipx exch def
  1045. y exch get /taily exch def
  1046. x exch get /tailx exch def
  1047. brushRightArrow { tipx tipy tailx taily arrowhead } if
  1048. end
  1049. } dup 0 4 dict put def
  1052. /arrowHeight 10 def
  1053. /arrowWidth 5 def
  1055. /IdrawDict 51 dict def
  1056. IdrawDict begin
  1058. /reencodeISO {
  1059. dup dup findfont dup length dict begin
  1060. { 1 index /FID ne { def }{ pop pop } ifelse } forall
  1061. /Encoding ISOLatin1Encoding def
  1062. currentdict end definefont
  1063. } def
  1065. /ISOLatin1Encoding [
  1066. /.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef
  1067. /.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef
  1068. /.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef
  1069. /.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef
  1070. /space/exclam/quotedbl/numbersign/dollar/percent/ampersand/quoteright
  1071. /parenleft/parenright/asterisk/plus/comma/minus/period/slash
  1072. /zero/one/two/three/four/five/six/seven/eight/nine/colon/semicolon
  1073. /less/equal/greater/question/at/A/B/C/D/E/F/G/H/I/J/K/L/M/N
  1074. /O/P/Q/R/S/T/U/V/W/X/Y/Z/bracketleft/backslash/bracketright
  1075. /asciicircum/underscore/quoteleft/a/b/c/d/e/f/g/h/i/j/k/l/m
  1076. /n/o/p/q/r/s/t/u/v/w/x/y/z/braceleft/bar/braceright/asciitilde
  1077. /.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef
  1078. /.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef
  1079. /.notdef/dotlessi/grave/acute/circumflex/tilde/macron/breve
  1080. /dotaccent/dieresis/.notdef/ring/cedilla/.notdef/hungarumlaut
  1081. /ogonek/caron/space/exclamdown/cent/sterling/currency/yen/brokenbar
  1082. /section/dieresis/copyright/ordfeminine/guillemotleft/logicalnot
  1083. /hyphen/registered/macron/degree/plusminus/twosuperior/threesuperior
  1084. /acute/mu/paragraph/periodcentered/cedilla/onesuperior/ordmasculine
  1085. /guillemotright/onequarter/onehalf/threequarters/questiondown
  1086. /Agrave/Aacute/Acircumflex/Atilde/Adieresis/Aring/AE/Ccedilla
  1087. /Egrave/Eacute/Ecircumflex/Edieresis/Igrave/Iacute/Icircumflex
  1088. /Idieresis/Eth/Ntilde/Ograve/Oacute/Ocircumflex/Otilde/Odieresis
  1089. /multiply/Oslash/Ugrave/Uacute/Ucircumflex/Udieresis/Yacute
  1090. /Thorn/germandbls/agrave/aacute/acircumflex/atilde/adieresis
  1091. /aring/ae/ccedilla/egrave/eacute/ecircumflex/edieresis/igrave
  1092. /iacute/icircumflex/idieresis/eth/ntilde/ograve/oacute/ocircumflex
  1093. /otilde/odieresis/divide/oslash/ugrave/uacute/ucircumflex/udieresis
  1094. /yacute/thorn/ydieresis
  1095. ] def
  1096. /Times-Italic reencodeISO def
  1098. /none null def
  1099. /numGraphicParameters 17 def
  1100. /stringLimit 65535 def
  1102. /Begin {
  1103. save
  1104. numGraphicParameters dict begin
  1105. } def
  1107. /End {
  1108. end
  1109. restore
  1110. } def
  1112. /SetB {
  1113. dup type /nulltype eq {
  1114. pop
  1115. false /brushRightArrow idef
  1116. false /brushLeftArrow idef
  1117. true /brushNone idef
  1118. } {
  1119. /brushDashOffset idef
  1120. /brushDashArray idef
  1121. 0 ne /brushRightArrow idef
  1122. 0 ne /brushLeftArrow idef
  1123. /brushWidth idef
  1124. false /brushNone idef
  1125. } ifelse
  1126. } def
  1128. /SetCFg {
  1129. /fgblue idef
  1130. /fggreen idef
  1131. /fgred idef
  1132. } def
  1134. /SetCBg {
  1135. /bgblue idef
  1136. /bggreen idef
  1137. /bgred idef
  1138. } def
  1140. /SetF {
  1141. /printSize idef
  1142. /printFont idef
  1143. } def
  1145. /SetP {
  1146. dup type /nulltype eq {
  1147. pop true /patternNone idef
  1148. } {
  1149. dup -1 eq {
  1150. /patternGrayLevel idef
  1151. /patternString idef
  1152. } {
  1153. /patternGrayLevel idef
  1154. } ifelse
  1155. false /patternNone idef
  1156. } ifelse
  1157. } def
  1159. /BSpl {
  1160. 0 begin
  1161. storexyn
  1162. newpath
  1163. n 1 gt {
  1164. 0 0 0 0 0 0 1 1 true subspline
  1165. n 2 gt {
  1166. 0 0 0 0 1 1 2 2 false subspline
  1167. 1 1 n 3 sub {
  1168. /i exch def
  1169. i 1 sub dup i dup i 1 add dup i 2 add dup false subspline
  1170. } for
  1171. n 3 sub dup n 2 sub dup n 1 sub dup 2 copy false subspline
  1172. } if
  1173. n 2 sub dup n 1 sub dup 2 copy 2 copy false subspline
  1174. patternNone not brushLeftArrow not brushRightArrow not and and { ifill } if
  1175. brushNone not { istroke } if
  1176. 0 0 1 1 leftarrow
  1177. n 2 sub dup n 1 sub dup rightarrow
  1178. } if
  1179. end
  1180. } dup 0 4 dict put def
  1182. /Circ {
  1183. newpath
  1184. 0 360 arc
  1185. patternNone not { ifill } if
  1186. brushNone not { istroke } if
  1187. } def
  1189. /CBSpl {
  1190. 0 begin
  1191. dup 2 gt {
  1192. storexyn
  1193. newpath
  1194. n 1 sub dup 0 0 1 1 2 2 true subspline
  1195. 1 1 n 3 sub {
  1196. /i exch def
  1197. i 1 sub dup i dup i 1 add dup i 2 add dup false subspline
  1198. } for
  1199. n 3 sub dup n 2 sub dup n 1 sub dup 0 0 false subspline
  1200. n 2 sub dup n 1 sub dup 0 0 1 1 false subspline
  1201. patternNone not { ifill } if
  1202. brushNone not { istroke } if
  1203. } {
  1204. Poly
  1205. } ifelse
  1206. end
  1207. } dup 0 4 dict put def
  1209. /Elli {
  1210. 0 begin
  1211. newpath
  1212. 4 2 roll
  1213. translate
  1214. scale
  1215. 0 0 1 0 360 arc
  1216. patternNone not { ifill } if
  1217. brushNone not { istroke } if
  1218. end
  1219. } dup 0 1 dict put def
  1221. /Line {
  1222. 0 begin
  1223. 2 storexyn
  1224. newpath
  1225. x 0 get y 0 get moveto
  1226. x 1 get y 1 get lineto
  1227. brushNone not { istroke } if
  1228. 0 0 1 1 leftarrow
  1229. 0 0 1 1 rightarrow
  1230. end
  1231. } dup 0 4 dict put def
  1233. /MLine {
  1234. 0 begin
  1235. storexyn
  1236. newpath
  1237. n 1 gt {
  1238. x 0 get y 0 get moveto
  1239. 1 1 n 1 sub {
  1240. /i exch def
  1241. x i get y i get lineto
  1242. } for
  1243. patternNone not brushLeftArrow not brushRightArrow not and and { ifill } if
  1244. brushNone not { istroke } if
  1245. 0 0 1 1 leftarrow
  1246. n 2 sub dup n 1 sub dup rightarrow
  1247. } if
  1248. end
  1249. } dup 0 4 dict put def
  1251. /Poly {
  1252. 3 1 roll
  1253. newpath
  1254. moveto
  1255. -1 add
  1256. { lineto } repeat
  1257. closepath
  1258. patternNone not { ifill } if
  1259. brushNone not { istroke } if
  1260. } def
  1262. /Rect {
  1263. 0 begin
  1264. /t exch def
  1265. /r exch def
  1266. /b exch def
  1267. /l exch def
  1268. newpath
  1269. l b moveto
  1270. l t lineto
  1271. r t lineto
  1272. r b lineto
  1273. closepath
  1274. patternNone not { ifill } if
  1275. brushNone not { istroke } if
  1276. end
  1277. } dup 0 4 dict put def
  1279. /Text {
  1280. ishow
  1281. } def
  1283. /idef {
  1284. dup where { pop pop pop } { exch def } ifelse
  1285. } def
  1287. /ifill {
  1288. 0 begin
  1289. gsave
  1290. patternGrayLevel -1 ne {
  1291. fgred bgred fgred sub patternGrayLevel mul add
  1292. fggreen bggreen fggreen sub patternGrayLevel mul add
  1293. fgblue bgblue fgblue sub patternGrayLevel mul add setrgbcolor
  1294. eofill
  1295. } {
  1296. eoclip
  1297. originalCTM setmatrix
  1298. pathbbox /t exch def /r exch def /b exch def /l exch def
  1299. /w r l sub ceiling cvi def
  1300. /h t b sub ceiling cvi def
  1301. /imageByteWidth w 8 div ceiling cvi def
  1302. /imageHeight h def
  1303. bgred bggreen bgblue setrgbcolor
  1304. eofill
  1305. fgred fggreen fgblue setrgbcolor
  1306. w 0 gt h 0 gt and {
  1307. l w add b translate w neg h scale
  1308. w h true [w 0 0 h neg 0 h] { patternproc } imagemask
  1309. } if
  1310. } ifelse
  1311. grestore
  1312. end
  1313. } dup 0 8 dict put def
  1315. /istroke {
  1316. gsave
  1317. brushDashOffset -1 eq {
  1318. [] 0 setdash
  1319. 1 setgray
  1320. } {
  1321. brushDashArray brushDashOffset setdash
  1322. fgred fggreen fgblue setrgbcolor
  1323. } ifelse
  1324. brushWidth setlinewidth
  1325. originalCTM setmatrix
  1326. stroke
  1327. grestore
  1328. } def
  1330. /ishow {
  1331. 0 begin
  1332. gsave
  1333. fgred fggreen fgblue setrgbcolor
  1334. /fontDict printFont printSize scalefont dup setfont def
  1335. /descender fontDict begin 0 [FontBBox] 1 get FontMatrix end
  1336. transform exch pop def
  1337. /vertoffset 1 printSize sub descender sub def {
  1338. 0 vertoffset moveto show
  1339. /vertoffset vertoffset printSize sub def
  1340. } forall
  1341. grestore
  1342. end
  1343. } dup 0 3 dict put def
  1344. /patternproc {
  1345. 0 begin
  1346. /patternByteLength patternString length def
  1347. /patternHeight patternByteLength 8 mul sqrt cvi def
  1348. /patternWidth patternHeight def
  1349. /patternByteWidth patternWidth 8 idiv def
  1350. /imageByteMaxLength imageByteWidth imageHeight mul
  1351. stringLimit patternByteWidth sub min def
  1352. /imageMaxHeight imageByteMaxLength imageByteWidth idiv patternHeight idiv
  1353. patternHeight mul patternHeight max def
  1354. /imageHeight imageHeight imageMaxHeight sub store
  1355. /imageString imageByteWidth imageMaxHeight mul patternByteWidth add string def
  1356. 0 1 imageMaxHeight 1 sub {
  1357. /y exch def
  1358. /patternRow y patternByteWidth mul patternByteLength mod def
  1359. /patternRowString patternString patternRow patternByteWidth getinterval def
  1360. /imageRow y imageByteWidth mul def
  1361. 0 patternByteWidth imageByteWidth 1 sub {
  1362. /x exch def
  1363. imageString imageRow x add patternRowString putinterval
  1364. } for
  1365. } for
  1366. imageString
  1367. end
  1368. } dup 0 12 dict put def
  1370. /min {
  1371. dup 3 2 roll dup 4 3 roll lt { exch } if pop
  1372. } def
  1374. /max {
  1375. dup 3 2 roll dup 4 3 roll gt { exch } if pop
  1376. } def
  1378. /midpoint {
  1379. 0 begin
  1380. /y1 exch def
  1381. /x1 exch def
  1382. /y0 exch def
  1383. /x0 exch def
  1384. x0 x1 add 2 div
  1385. y0 y1 add 2 div
  1386. end
  1387. } dup 0 4 dict put def
  1389. /thirdpoint {
  1390. 0 begin
  1391. /y1 exch def
  1392. /x1 exch def
  1393. /y0 exch def
  1394. /x0 exch def
  1395. x0 2 mul x1 add 3 div
  1396. y0 2 mul y1 add 3 div
  1397. end
  1398. } dup 0 4 dict put def
  1400. /subspline {
  1401. 0 begin
  1402. /movetoNeeded exch def
  1403. y exch get /y3 exch def
  1404. x exch get /x3 exch def
  1405. y exch get /y2 exch def
  1406. x exch get /x2 exch def
  1407. y exch get /y1 exch def
  1408. x exch get /x1 exch def
  1409. y exch get /y0 exch def
  1410. x exch get /x0 exch def
  1411. x1 y1 x2 y2 thirdpoint
  1412. /p1y exch def
  1413. /p1x exch def
  1414. x2 y2 x1 y1 thirdpoint
  1415. /p2y exch def
  1416. /p2x exch def
  1417. x1 y1 x0 y0 thirdpoint
  1418. p1x p1y midpoint
  1419. /p0y exch def
  1420. /p0x exch def
  1421. x2 y2 x3 y3 thirdpoint
  1422. p2x p2y midpoint
  1423. /p3y exch def
  1424. /p3x exch def
  1425. movetoNeeded { p0x p0y moveto } if
  1426. p1x p1y p2x p2y p3x p3y curveto
  1427. end
  1428. } dup 0 17 dict put def
  1430. /storexyn {
  1431. /n exch def
  1432. /y n array def
  1433. /x n array def
  1434. n 1 sub -1 0 {
  1435. /i exch def
  1436. y i 3 2 roll put
  1437. x i 3 2 roll put
  1438. } for
  1439. } def
  1441. /SSten {
  1442. fgred fggreen fgblue setrgbcolor
  1443. dup true exch 1 0 0 -1 0 6 -1 roll matrix astore
  1444. } def
  1446. /FSten {
  1447. dup 3 -1 roll dup 4 1 roll exch
  1448. newpath
  1449. 0 0 moveto
  1450. dup 0 exch lineto
  1451. exch dup 3 1 roll exch lineto
  1452. 0 lineto
  1453. closepath
  1454. bgred bggreen bgblue setrgbcolor
  1455. eofill
  1456. SSten
  1457. } def
  1459. /Rast {
  1460. exch dup 3 1 roll 1 0 0 -1 0 6 -1 roll matrix astore
  1461. } def
  1464. %I Idraw 10 Grid 8 8 
  1467. Begin
  1468. %I b u
  1469. %I cfg u
  1470. %I cbg u
  1471. %I f u
  1472. %I p u
  1473. %I t
  1474. [ 0.796717 0 0 0.796717 0 0 ] concat
  1475. /originalCTM matrix currentmatrix def
  1477. Begin %I Line
  1478. %I b 65535
  1479. 2 0 0 [] 0 SetB
  1480. %I cfg Black
  1481. 0 0 0 SetCFg
  1482. %I cbg White
  1483. 1 1 1 SetCBg
  1484. %I p
  1485. 1 SetP
  1486. %I t
  1487. [ 1 -0 -0 1 82 209 ] concat
  1488. %I
  1489. 238 287 310 351 Line
  1490. %I 1
  1491. End
  1493. Begin %I Line
  1494. %I b 65535
  1495. 2 0 0 [] 0 SetB
  1496. %I cfg Black
  1497. 0 0 0 SetCFg
  1498. %I cbg White
  1499. 1 1 1 SetCBg
  1500. %I p
  1501. 1 SetP
  1502. %I t
  1503. [ 1 -0 -0 1 82 209 ] concat
  1504. %I
  1505. 366 479 310 351 Line
  1506. %I 1
  1507. End
  1509. Begin %I Rect
  1510. %I b 65535
  1511. 1 0 0 [] 0 SetB
  1512. %I cfg Black
  1513. 0 0 0 SetCFg
  1514. %I cbg White
  1515. 1 1 1 SetCBg
  1516. none SetP %I p n
  1517. %I t
  1518. [ 1 -0 -0 1 90 105 ] concat
  1519. %I
  1520. 182 359 278 455 Rect
  1521. End
  1523. Begin %I Rect
  1524. %I b 65535
  1525. 1 0 0 [] 0 SetB
  1526. %I cfg Black
  1527. 0 0 0 SetCFg
  1528. %I cbg White
  1529. 1 1 1 SetCBg
  1530. none SetP %I p n
  1531. %I t
  1532. [ 1 -0 -0 1 82 209 ] concat
  1533. %I
  1534. 182 359 278 455 Rect
  1535. End
  1537. Begin %I Rect
  1538. %I b 65535
  1539. 2 0 0 [] 0 SetB
  1540. %I cfg Black
  1541. 0 0 0 SetCFg
  1542. %I cbg White
  1543. 1 1 1 SetCBg
  1544. %I p
  1545. < 88 44 22 11 88 44 22 11 > -1 SetP
  1546. %I t
  1547. [ 1 -0 -0 1 162 153 ] concat
  1548. %I
  1549. 182 359 278 455 Rect
  1550. End
  1552. Begin %I Elli
  1553. %I b 65535
  1554. 1 0 0 [] 0 SetB
  1555. %I cfg Black
  1556. 0 0 0 SetCFg
  1557. %I cbg White
  1558. 1 1 1 SetCBg
  1559. %I p
  1560. 0 SetP
  1561. %I t
  1562. [ 0.5 -0 -0 0.5 224 457.5 ] concat
  1563. %I
  1564. 176 317 7 7 Elli
  1565. End
  1567. Begin %I Elli
  1568. %I b 65535
  1569. 1 0 0 [] 0 SetB
  1570. %I cfg Black
  1571. 0 0 0 SetCFg
  1572. %I cbg White
  1573. 1 1 1 SetCBg
  1574. %I p
  1575. 0 SetP
  1576. %I t
  1577. [ 0.5 -0 -0 0.5 360 529.5 ] concat
  1578. %I
  1579. 176 317 7 7 Elli
  1580. End
  1582. Begin %I Elli
  1583. %I b 65535
  1584. 1 0 0 [] 0 SetB
  1585. %I cfg Black
  1586. 0 0 0 SetCFg
  1587. %I cbg White
  1588. 1 1 1 SetCBg
  1589. %I p
  1590. 0 SetP
  1591. %I t
  1592. [ 0.5 -0 -0 0.5 232 337.5 ] concat
  1593. %I
  1594. 176 317 7 7 Elli
  1595. End
  1597. Begin %I Elli
  1598. %I b 65535
  1599. 1 0 0 [] 0 SetB
  1600. %I cfg Black
  1601. 0 0 0 SetCFg
  1602. %I cbg White
  1603. 1 1 1 SetCBg
  1604. %I p
  1605. 0 SetP
  1606. %I t
  1607. [ 0.5 -0 -0 0.5 168 529.5 ] concat
  1608. %I
  1609. 176 317 7 7 Elli
  1610. End
  1612. Begin %I Rect
  1613. %I b 65535
  1614. 2 0 0 [] 0 SetB
  1615. %I cfg Black
  1616. 0 0 0 SetCFg
  1617. %I cbg White
  1618. 1 1 1 SetCBg
  1619. none SetP %I p n
  1620. %I t
  1621. [ 1 -0 -0 1 82 209 ] concat
  1622. %I
  1623. 134 255 398 519 Rect
  1624. End
  1626. Begin %I Rect
  1627. %I b 65535
  1628. 1 0 0 [] 0 SetB
  1629. %I cfg Black
  1630. 0 0 0 SetCFg
  1631. %I cbg White
  1632. 1 1 1 SetCBg
  1633. none SetP %I p n
  1634. %I t
  1635. [ 1 -0 -0 1 34 273 ] concat
  1636. %I
  1637. 182 359 278 455 Rect
  1638. End
  1640. Begin %I Rect
  1641. %I b 65535
  1642. 1 0 0 [] 0 SetB
  1643. %I cfg Black
  1644. 0 0 0 SetCFg
  1645. %I cbg White
  1646. 1 1 1 SetCBg
  1647. none SetP %I p n
  1648. %I t
  1649. [ 1 -0 -0 1 202 273 ] concat
  1650. %I
  1651. 182 359 278 455 Rect
  1652. End
  1654. Begin %I Line
  1655. %I b 65535
  1656. 2 0 0 [] 0 SetB
  1657. %I cfg Black
  1658. 0 0 0 SetCFg
  1659. %I cbg White
  1660. 1 1 1 SetCBg
  1661. %I p
  1662. 1 SetP
  1663. %I t
  1664. [ 1 -0 -0 1 82 209 ] concat
  1665. %I
  1666. 174 479 366 479 Line
  1667. %I 1
  1668. End
  1670. Begin %I Line
  1671. %I b 65535
  1672. 2 0 0 [] 0 SetB
  1673. %I cfg Black
  1674. 0 0 0 SetCFg
  1675. %I cbg White
  1676. 1 1 1 SetCBg
  1677. %I p
  1678. 1 SetP
  1679. %I t
  1680. [ 1 -0 -0 1 82 209 ] concat
  1681. %I
  1682. 366 479 230 407 Line
  1683. %I 1
  1684. End
  1686. Begin %I Line
  1687. %I b 65535
  1688. 2 0 0 [] 0 SetB
  1689. %I cfg Black
  1690. 0 0 0 SetCFg
  1691. %I cbg White
  1692. 1 1 1 SetCBg
  1693. %I p
  1694. 1 SetP
  1695. %I t
  1696. [ 1 -0 -0 1 82 209 ] concat
  1697. %I
  1698. 174 479 238 287 Line
  1699. %I 1
  1700. End
  1702. Begin %I Elli
  1703. %I b 65535
  1704. 1 0 0 [] 0 SetB
  1705. %I cfg Black
  1706. 0 0 0 SetCFg
  1707. %I cbg White
  1708. 1 1 1 SetCBg
  1709. %I p
  1710. 0 SetP
  1711. %I t
  1712. [ 0.5 -0 -0 0.5 176 401.5 ] concat
  1713. %I
  1714. 176 317 7 7 Elli
  1715. End
  1717. Begin %I Rect
  1718. %I b 65535
  1719. 1 0 0 [] 0 SetB
  1720. %I cfg Black
  1721. 0 0 0 SetCFg
  1722. %I cbg White
  1723. 1 1 1 SetCBg
  1724. none SetP %I p n
  1725. %I t
  1726. [ 1 -0 -0 1 34 153 ] concat
  1727. %I
  1728. 182 359 278 455 Rect
  1729. End
  1731. Begin %I Line
  1732. %I b 65535
  1733. 2 0 0 [] 0 SetB
  1734. %I cfg Black
  1735. 0 0 0 SetCFg
  1736. %I cbg White
  1737. 1 1 1 SetCBg
  1738. %I p
  1739. 1 SetP
  1740. %I t
  1741. [ 1 -0 -0 1 82 209 ] concat
  1742. %I
  1743. 182 351 238 287 Line
  1744. %I 1
  1745. End
  1747. Begin %I Line
  1748. %I b 65535
  1749. 2 0 0 [] 0 SetB
  1750. %I cfg Black
  1751. 0 0 0 SetCFg
  1752. %I cbg White
  1753. 1 1 1 SetCBg
  1754. %I p
  1755. 1 SetP
  1756. %I t
  1757. [ 1 -0 -0 1 82 209 ] concat
  1758. %I
  1759. 230 407 182 351 Line
  1760. %I 1
  1761. End
  1763. Begin %I Elli
  1764. %I b 65535
  1765. 1 0 0 [] 0 SetB
  1766. %I cfg Black
  1767. 0 0 0 SetCFg
  1768. %I cbg White
  1769. 1 1 1 SetCBg
  1770. %I p
  1771. 0 SetP
  1772. %I t
  1773. [ 0.5 -0 -0 0.5 264 441.5 ] concat
  1774. %I
  1775. 176 317 7 7 Elli
  1776. End
  1778. Begin %I Elli
  1779. %I b 65535
  1780. 1 0 0 [] 0 SetB
  1781. %I cfg Black
  1782. 0 0 0 SetCFg
  1783. %I cbg White
  1784. 1 1 1 SetCBg
  1785. %I p
  1786. 0 SetP
  1787. %I t
  1788. [ 0.5 -0 -0 0.5 336 425.5 ] concat
  1789. %I
  1790. 176 317 7 7 Elli
  1791. End
  1793. Begin %I Elli
  1794. %I b 65535
  1795. 1 0 0 [] 0 SetB
  1796. %I cfg Black
  1797. 0 0 0 SetCFg
  1798. %I cbg White
  1799. 1 1 1 SetCBg
  1800. %I p
  1801. 0 SetP
  1802. %I t
  1803. [ 0.5 -0 -0 0.5 272 385.5 ] concat
  1804. %I
  1805. 176 317 7 7 Elli
  1806. End
  1808. Begin %I Line
  1809. %I b 65535
  1810. 1 0 0 [] 0 SetB
  1811. %I cfg Black
  1812. 0 0 0 SetCFg
  1813. %I cbg White
  1814. 1 1 1 SetCBg
  1815. none SetP %I p n
  1816. %I t
  1817. [ 1 -0 -0 1 82 209 ] concat
  1818. %I
  1819. 278 335 342 375 Line
  1820. %I 1
  1821. End
  1823. Begin %I Line
  1824. %I b 65535
  1825. 1 0 0 [] 0 SetB
  1826. %I cfg Black
  1827. 0 0 0 SetCFg
  1828. %I cbg White
  1829. 1 1 1 SetCBg
  1830. none SetP %I p n
  1831. %I t
  1832. [ 1 -0 -0 1 82 209 ] concat
  1833. %I
  1834. 270 391 342 375 Line
  1835. %I 1
  1836. End
  1838. Begin %I Line
  1839. %I b 65535
  1840. 1 1 1 [] 0 SetB
  1841. %I cfg Black
  1842. 0 0 0 SetCFg
  1843. %I cbg White
  1844. 1 1 1 SetCBg
  1845. %I p
  1846. 0 SetP
  1847. %I t
  1848. [ 1 -0 -0 1 82 173.5 ] concat
  1849. %I
  1850. 134 275 398 275 Line
  1851. %I 1
  1852. End
  1854. Begin %I Text
  1855. %I cfg Black
  1856. 0 0 0 SetCFg
  1857. %I f *-times-medium-i-*-120-*
  1858. Times-Italic 12 SetF
  1859. %I t
  1860. [ 1 0 0 1 336 444 ] concat
  1861. %I
  1862. [
  1863. (Scale)
  1864. ] Text
  1865. End
  1867. Begin %I Text
  1868. %I cfg Black
  1869. 0 0 0 SetCFg
  1870. %I f *-times-medium-i-*-120-*
  1871. Times-Italic 12 SetF
  1872. %I t
  1873. [ 1 0 0 1 280 476 ] concat
  1874. %I
  1875. [
  1876. (transfrac*Scale)
  1877. ] Text
  1878. End
  1880. Begin %I Text
  1881. %I cfg Black
  1882. 0 0 0 SetCFg
  1883. %I f *-times-medium-i-*-120-*
  1884. Times-Italic 12 SetF
  1885. %I t
  1886. [ 1 0 0 1 400 476 ] concat
  1887. %I
  1888. [
  1889. (stubfrac*Scale)
  1890. ] Text
  1891. End
  1893. Begin %I Line
  1894. %I b 65535
  1895. 1 1 1 [] 0 SetB
  1896. %I cfg Black
  1897. 0 0 0 SetCFg
  1898. %I cbg White
  1899. 1 1 1 SetCBg
  1900. %I p
  1901. 0 SetP
  1902. %I t
  1903. [ 0.5 -0 -0 0.5 229.5 423.5 ] concat
  1904. %I
  1905. 351 113 479 113 Line
  1906. %I 2
  1907. End
  1909. Begin %I Line
  1910. %I b 65535
  1911. 1 1 1 [] 0 SetB
  1912. %I cfg Black
  1913. 0 0 0 SetCFg
  1914. %I cbg White
  1915. 1 1 1 SetCBg
  1916. %I p
  1917. 0 SetP
  1918. %I t
  1919. [ 0.5 -0 -0 0.5 229 423.5 ] concat
  1920. %I
  1921. 95 113 271 113 Line
  1922. %I 2
  1923. End
  1925. Begin %I Rect
  1926. %I b 61680
  1927. 1 0 0 [4 4 4 4] 0 SetB
  1928. %I cfg Black
  1929. 0 0 0 SetCFg
  1930. %I cbg White
  1931. 1 1 1 SetCBg
  1932. %I p
  1933. 0.75 SetP
  1934. %I t
  1935. [ 1 -0 -0 1 136.5 254 ] concat
  1936. %I
  1937. 262 232 334 304 Rect
  1938. End
  1940. Begin %I Elli
  1941. %I b 65535
  1942. 1 0 0 [] 0 SetB
  1943. %I cfg Black
  1944. 0 0 0 SetCFg
  1945. %I cbg White
  1946. 1 1 1 SetCBg
  1947. %I p
  1948. 0 SetP
  1949. %I t
  1950. [ 0.5 -0 -0 0.5 328 369.5 ] concat
  1951. %I
  1952. 176 317 7 7 Elli
  1953. End
  1955. Begin %I Line
  1956. %I b 65535
  1957. 1 0 0 [] 0 SetB
  1958. %I cfg Black
  1959. 0 0 0 SetCFg
  1960. %I cbg White
  1961. 1 1 1 SetCBg
  1962. none SetP %I p n
  1963. %I t
  1964. [ 1 -0 -0 1 82 209 ] concat
  1965. %I
  1966. 342 375 334 319 Line
  1967. %I 1
  1968. End
  1970. Begin %I Line
  1971. %I b 65535
  1972. 1 0 0 [] 0 SetB
  1973. %I cfg Black
  1974. 0 0 0 SetCFg
  1975. %I cbg White
  1976. 1 1 1 SetCBg
  1977. none SetP %I p n
  1978. %I t
  1979. [ 1 -0 -0 1 82 209 ] concat
  1980. %I
  1981. 334 319 278 335 Line
  1982. %I 1
  1983. End
  1985. Begin %I Rect
  1986. %I b 61680
  1987. 1 0 0 [4 4 4 4] 0 SetB
  1988. %I cfg Black
  1989. 0 0 0 SetCFg
  1990. %I cbg White
  1991. 1 1 1 SetCBg
  1992. %I p
  1993. 0 SetP
  1994. %I t
  1995. [ 0.5 -0 -0 0.5 223 385.5 ] concat
  1996. %I
  1997. 431 314 438 321 Rect
  1998. End
  2000. Begin %I Rect
  2001. %I b 61680
  2002. 1 0 0 [4 4 4 4] 0 SetB
  2003. %I cfg Black
  2004. 0 0 0 SetCFg
  2005. %I cbg White
  2006. 1 1 1 SetCBg
  2007. %I p
  2008. 0 SetP
  2009. %I t
  2010. [ 0.5 -0 -0 0.5 239 377.5 ] concat
  2011. %I
  2012. 431 314 438 321 Rect
  2013. End
  2015. Begin %I Rect
  2016. %I b 61680
  2017. 1 0 0 [4 4 4 4] 0 SetB
  2018. %I cfg Black
  2019. 0 0 0 SetCFg
  2020. %I cbg White
  2021. 1 1 1 SetCBg
  2022. %I p
  2023. 0 SetP
  2024. %I t
  2025. [ 0.5 -0 -0 0.5 215 361.5 ] concat
  2026. %I
  2027. 431 314 438 321 Rect
  2028. End
  2030. Begin %I Rect
  2031. %I b 61680
  2032. 1 0 0 [4 4 4 4] 0 SetB
  2033. %I cfg Black
  2034. 0 0 0 SetCFg
  2035. %I cbg White
  2036. 1 1 1 SetCBg
  2037. %I p
  2038. 0 SetP
  2039. %I t
  2040. [ 0.5 -0 -0 0.5 191 361.5 ] concat
  2041. %I
  2042. 431 314 438 321 Rect
  2043. End
  2045. Begin %I Rect
  2046. %I b 61680
  2047. 1 0 0 [4 4 4 4] 0 SetB
  2048. %I cfg Black
  2049. 0 0 0 SetCFg
  2050. %I cbg White
  2051. 1 1 1 SetCBg
  2052. %I p
  2053. 0 SetP
  2054. %I t
  2055. [ 0.5 -0 -0 0.5 191 385.5 ] concat
  2056. %I
  2057. 431 314 438 321 Rect
  2058. End
  2060. Begin %I Rect
  2061. %I b 65535
  2062. 1 0 0 [] 0 SetB
  2063. %I cfg Black
  2064. 0 0 0 SetCFg
  2065. %I cbg White
  2066. 1 1 1 SetCBg
  2067. %I p
  2068. 0 SetP
  2069. %I t
  2070. [ 0.5 -0 -0 0.5 239 337.5 ] concat
  2071. %I
  2072. 431 314 438 321 Rect
  2073. End
  2075. Begin %I Line
  2076. %I b 65535
  2077. 1 0 0 [] 0 SetB
  2078. %I cfg Black
  2079. 0 0 0 SetCFg
  2080. %I cbg White
  2081. 1 1 1 SetCBg
  2082. %I p
  2083. 0 SetP
  2084. %I t
  2085. [ 0.5 -0 -0 0.5 232.5 423.5 ] concat
  2086. %I
  2087. 351 241 415 241 Line
  2088. %I 2
  2089. End
  2091. Begin %I Line
  2092. %I b 65535
  2093. 1 0 0 [] 0 SetB
  2094. %I cfg Black
  2095. 0 0 0 SetCFg
  2096. %I cbg White
  2097. 1 1 1 SetCBg
  2098. %I p
  2099. 0 SetP
  2100. %I t
  2101. [ 0.5 -0 -0 0.5 232.5 423.5 ] concat
  2102. %I
  2103. 415 241 447 225 Line
  2104. %I 2
  2105. End
  2107. Begin %I Line
  2108. %I b 65535
  2109. 1 0 0 [] 0 SetB
  2110. %I cfg Black
  2111. 0 0 0 SetCFg
  2112. %I cbg White
  2113. 1 1 1 SetCBg
  2114. %I p
  2115. 0 SetP
  2116. %I t
  2117. [ 0.5 -0 -0 0.5 232.5 423.5 ] concat
  2118. %I
  2119. 447 225 447 145 Line
  2120. %I 2
  2121. End
  2123. Begin %I Line
  2124. %I b 65535
  2125. 1 0 0 [] 0 SetB
  2126. %I cfg Black
  2127. 0 0 0 SetCFg
  2128. %I cbg White
  2129. 1 1 1 SetCBg
  2130. %I p
  2131. 0 SetP
  2132. %I t
  2133. [ 0.5 -0 -0 0.5 232.5 423.5 ] concat
  2134. %I
  2135. 351 193 447 145 Line
  2136. %I 2
  2137. End
  2139. Begin %I Line
  2140. %I b 65535
  2141. 1 0 0 [] 0 SetB
  2142. %I cfg Black
  2143. 0 0 0 SetCFg
  2144. %I cbg White
  2145. 1 1 1 SetCBg
  2146. %I p
  2147. 0 SetP
  2148. %I t
  2149. [ 0.5 -0 -0 0.5 232.5 423.5 ] concat
  2150. %I
  2151. 367 209 351 241 Line
  2152. %I 2
  2153. End
  2155. Begin %I Line
  2156. %I b 65535
  2157. 1 0 0 [] 0 SetB
  2158. %I cfg Black
  2159. 0 0 0 SetCFg
  2160. %I cbg White
  2161. 1 1 1 SetCBg
  2162. %I p
  2163. 0 SetP
  2164. %I t
  2165. [ 0.5 -0 -0 0.5 232.5 423.5 ] concat
  2166. %I
  2167. 415 241 399 193 Line
  2168. %I 2
  2169. End
  2171. Begin %I Line
  2172. %I b 65535
  2173. 1 0 0 [] 0 SetB
  2174. %I cfg Black
  2175. 0 0 0 SetCFg
  2176. %I cbg White
  2177. 1 1 1 SetCBg
  2178. %I p
  2179. 0 SetP
  2180. %I t
  2181. [ 0.5 -0 -0 0.5 232.5 423.5 ] concat
  2182. %I
  2183. 351 193 447 225 Line
  2184. %I 2
  2185. End
  2187. End %I eop
  2189. showpage
  2192. end
  2193. %%EndDocument
  2195.  endTexFig
  2196.  628 1364 a Fj(Figure)15 b(3:)20 b(T)l(ransit)15 b(Stub)h(La)o(y)o(out)
  2197. 30 1501 y Fl(References)30 1603 y Fj([1])22 b(Matthew)15
  2198. b(Doar)h(and)h(Ian)g(Leslie.)26 b(Ho)o(w)16 b(bad)h(is)g(naiv)o(e)g(m)o
  2199. (ulticast)g(routing?)33 b(In)18 b Fb(Pr)n(o)n(c)n(e)n(e)n(dings)d(of)
  2200. 101 1659 y(IEEE)g(INF)o(OCOM)f('93)p Fj(,)h(pages)g(82{89,)f(1993.)30
  2201. 1753 y([2])22 b(Bernard)d(M.)f(W)l(axman.)30 b(Routing)19
  2202. b(of)f(m)o(ultip)q(oin)o(t)i(connections.)32 b Fb(IEEE)19
  2203. b(Journal)g(on)h(Sele)n(cte)n(d)101 1809 y(A)o(r)n(e)n(as)15
  2204. b(in)h(Communic)n(ations)p Fj(,)e(6(9):1617{1)o(622,)d(1988.)30
  2205. 1903 y([3])22 b(Liming)c(W)l(ei)g(and)f(Deb)q(orah)g(Estrin.)25
  2206. b(The)18 b(trade-o13s)d(of)i(m)o(ulticast)g(trees)g(and)g
  2207. (algorithms.)25 b(In)101 1960 y Fb(International)15 b(Confer)n(enc)n(e)
  2208. f(on)i(Computer)h(Communic)n(ations)e(and)i(Networks)p
  2209. Fj(,)d(August)h(1994.)919 2940 y(6)p eop
  2210. %%Trailer
  2211. end
  2212. userdict /end-hook known{end-hook}if
  2213. %%EOF