(12) United States Patent
`Salama et al.
`
`I 1111111111111111 11111 lllll 111111111111111 11111 lllll 111111111111111 11111111
`US006584093Bl
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 6,584,093 Bl
`Jun.24,2003
`
`(54) METHOD AND APPARATUS FOR
`AUTOMATIC INTER-DOMAIN ROUTING OF
`CALLS
`
`(75)
`
`Inventors: Hussein Farouk Salama, Sunnyvale,
`CA (US); David R. Oran, Acton, MA
`(US); Dhaval N. Shah, Santa Clara, CA
`(US)
`
`(73) Assignee: Cisco Technology, Inc., San Jose, CA
`(US)
`
`( *) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21) Appl. No.: 09/225,921
`
`(22)
`
`Filed:
`
`Jan. 5, 1999
`
`(60)
`
`(51)
`(52)
`(58)
`
`(56)
`
`Related U.S. Application Data
`Provisional application No. 60/097,866, filed on Aug. 25,
`1998.
`
`Int. Cl.7 ................................................ H04L 12/28
`U.S. Cl. ........................................ 370/351; 370/466
`Field of Search .............................. 370/238.1, 465,
`370/466, 467, 469, 389, 392, 351, 352,
`353,354,355,356
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`5,361,256 A * 11/1994 Doeringer et al. ............ 370/60
`5,519,704 A * 5/1996 Farinacci et al.
`........ 370/85.13
`5,881,243 A * 3/1999 Zaumen et al. ........ 395/200.71
`6,339,595 Bl * 1/2002 Rekhter ...................... 370/392
`
`6,351,465 Bl * 2/2002 Han ........................... 370/395
`* cited by examiner
`Primary Examiner---Alpus H. Hsu
`Assistant Examiner-Thien Tran
`(74) Attorney, Agent, or Firm---Marger
`McCollom, P.C.
`(57)
`
`ABSTRACT
`
`Johnson &
`
`A method and apparatus for inter-domain routing of calls in
`a network, where the network represents a first wide area
`network. A routing node of the network advertises its access
`to a range of addresses in a second wide area network and
`a cost for access to the range of addresses to all adjacent
`nodes in the network. Each of the adjacent nodes inserts an
`entry in its own routing table associating access to the range
`of addresses in the second wide area network with the
`network address of the routing node and the cost for access.
`Each adjacent node then modifies the cost for access by
`adding its own cost and advertises its access to the range of
`addresses in the second wide area network and the modified
`cost for access to all of its adjacent nodes. When a call
`addressed to a destination address in the range of address in
`the second wide area network is received at each node of the
`network, then the node searches for the entry in its routing
`table corresponding to the range of addresses in the second
`wide area network having the lowest cost for access and
`connects the call to the adjacent node associated with the
`entry having the lowest cost. The routing node can also
`advertise one or more protocol types which it can support,
`where the protocol types are associated with the routing
`node in the routing table in each adjacent node and a call
`having a given protocol type is also routed at each node of
`the network based upon its protocol type.
`
`29 Claims, 17 Drawing Sheets
`
`1950
`
`1954
`
`2030
`
`2000
`
`/
`
`ETBGP
`
`ETBGP
`
`Ex.1019
`CISCO SYSTEMS, INC. / Page 1 of 35
`
`

`

`U.S. Patent
`
`Jun.24,2003
`
`Sheet 1 of 17
`
`US 6,584,093 Bl
`
`, - - - - , a
`
`(cid:143) (cid:143)
`
`,._ __ ....,, D
`
`(D _.
`
`<( z -:::E
`
`a::
`w
`t-
`
`0 ""
`
`0
`N
`
`t(cid:173)
`..... a::
`• <(
`
`tJ a:: -o
`LL -a::
`a..
`
`0
`,-
`
`N
`N
`
`0 ~\
`
`N
`,-
`
`. - - - - - , a
`
`(cid:143) (cid:143)
`
`L -__ _. D
`
`<( _.
`
`<(
`
`z -:::E
`
`a::
`w
`t-
`
`Ex.1019
`CISCO SYSTEMS, INC. / Page 2 of 35
`
`

`

`U.S. Patent
`
`Jun.24,2003
`
`Sheet 2 of 17
`
`US 6,584,093 Bl
`
`<(
`
`..-
`
`0
`
`~\
`
`N
`c., w N
`~
`w
`I-
`<(
`c.,
`
`(/)
`<(
`
`..-
`I")
`0)
`
`.
`
`~-£Ji
`
`(cid:143) (cid:143)
`<==>~ ¢::=> 2=>
`
`C
`
`0
`
`LO
`...,..
`N
`
`CD
`...J
`<(
`z
`1-t
`::E
`a::
`w
`I-
`
`<(
`1-t
`0
`w
`
`1--1
`
`I-
`::E
`(/) a::
`w
`:::> LL
`0 z
`w 0
`a::
`(..)
`z z
`0
`0
`1-4
`1--1
`(/)
`(/)
`(/)
`(/)
`1-t
`1-t
`::E
`::E
`0
`0
`<( <(
`
`a..
`:::>
`I-
`w
`(/)
`
`I-
`u
`w
`z
`z
`0
`()
`
`w
`c.,
`0
`w
`...J
`3:
`w
`...J 0 w
`c.,
`z z z
`<( z ~
`<( u
`I
`u
`<(
`:c
`X
`...J
`()
`w
`w
`...J z
`w <( z
`(/)
`1-t u <(
`:c
`I-
`1-t c.,
`()
`...J 0
`...J
`1-t
`...J
`CD
`<( z
`<(
`()
`a.. w
`<( a.. c.,
`1-1
`(..) 0
`0
`...J
`z
`w
`a..
`0
`
`1-t
`
`::E ~
`::E
`<(
`<( <( w
`w w a::
`a:: a:
`I-
`I-
`I-
`(/)
`(/)
`(/)
`a..
`a.. a..
`(..)
`I-
`I-
`I-
`a:: a:: a::
`
`I-
`<""I a::
`• <(
`0 a::
`_o
`LL et
`-
`a..
`
`N .....
`
`, - - - - - , C
`
`(cid:143)
`(cid:143) L - - - - . . . .1 0
`
`<(
`
`...J
`
`<( z
`1-4
`::E
`a::
`w
`I-
`
`Ex.1019
`CISCO SYSTEMS, INC. / Page 3 of 35
`
`

`

`U.S. Patent
`
`Jun.24,2003
`
`Sheet 3 of 17
`
`US 6,584,093 Bl
`
`N
`N
`
`N .....
`
`. - - - - - . 0
`
`(cid:143) (cid:143)
`
`.__ __ _, D
`
`<.O
`N
`
`>(cid:173)
`x
`OCD
`0:: a.
`
`0
`I")
`
`<.O -
`
`>(cid:173)x
`
`O<C
`0::
`Q.
`
`. - - - - - . 0
`
`(cid:143) (cid:143)
`
`.__ __ _, D
`
`CD
`....I
`<(
`z
`1-1
`~
`0::
`w
`I-
`
`0
`N
`
`t-
`~ 0::
`• <
`0 0: _o
`LL ......
`0:
`a.
`
`0 .....
`
`<
`....I
`< z
`
`1-1
`~
`0::
`w
`I-
`
`Ex.1019
`CISCO SYSTEMS, INC. / Page 4 of 35
`
`

`

`U.S. Patent
`
`Jun.24,2003
`
`Sheet 4 of 17
`
`US 6,584,093 Bl
`
`N
`N
`
`0 ~,
`
`v
`U') v
`
`v n
`v
`
`,q-....
`
`C
`
`(cid:143) (cid:143)
`
`(cid:143)
`
`(0
`N
`
`>-
`X
`0 a::
`a.
`
`(0
`
`.....
`
`>-
`X
`0
`a::
`a.
`
`----.c
`
`(cid:143) (cid:143)
`
`----'(cid:143)
`
`al
`....J
`
`1--1
`
`<( z
`~ a::
`w
`I-
`
`tO v
`v
`
`>-
`X
`0 a::
`a.
`
`>-
`X
`0 a::
`a.
`
`tO n
`""""
`
`0
`N
`
`0
`
`T"""
`
`<(
`
`v
`v
`v
`
`::::t'.:
`c.,
`
`-I-
`~ a::
`• <(
`l? a:: - 0
`
`LL. 1--1 a::
`a..
`
`....J
`
`1--1
`
`<( z
`~ a::
`w
`I-
`
`Ex.1019
`CISCO SYSTEMS, INC. / Page 5 of 35
`
`

`

`U.S. Patent
`
`Jun.24,2003
`
`Sheet 5 of 17
`
`US 6,584,093 Bl
`
`(cid:143)
`
`(cid:143) (cid:143)
`
`0
`
`N
`N
`I.()
`
`0
`
`~\
`
`aJ
`w
`z
`0
`:r:
`a..
`w
`.....J
`w
`I-
`
`N
`N
`(0
`
`.....J
`<(
`z
`H
`~
`0:::
`w
`I-
`ti)
`N
`ti)
`
`.
`:r: ~\
`
`0
`
`0
`N
`(0
`
`(0
`N
`(0
`
`>-
`<(
`3:
`wm
`I-
`<(
`c.,
`
`I-
`\0 0:::
`• <(
`0 0:::
`_o
`LL a:
`a..
`
`v
`
`ti)
`I.()
`
`0
`ti)
`I.()
`
`(0
`
`.....
`
`I.()
`
`w
`z
`0
`:r:
`a..
`w
`.....J
`w
`I-
`
`(cid:143)(cid:143) o(cid:143)(cid:143)
`
`OD DD
`
`N
`.....
`I.()
`
`>-
`<(
`3:
`w
`I-
`<(
`c.,
`
`I-
`Lr) 0:::
`• <(
`0 0:::
`_o
`LL a:
`a..
`
`0
`.....
`
`I.()
`
`v
`ti)
`(0
`
`<(
`w
`z
`0
`:r:
`a..
`w
`.....J w
`I-
`
`N .....
`
`I.()
`
`>-
`<(
`3:
`w<C
`I--
`<(
`c.,
`
`0
`ti)
`(0
`
`0
`.....
`
`I.()
`
`U)
`
`.....
`
`I.()
`
`Ex.1019
`CISCO SYSTEMS, INC. / Page 6 of 35
`
`

`

`U.S. Patent
`
`Jun.24,2003
`
`Sheet 6 of 17
`
`US 6,584,093 Bl
`
`C
`
`(cid:143)
`
`D
`
`CD
`_J
`
`<( z
`
`1-t
`~
`0:
`w
`I-
`
`(cid:143)
`
`N
`
`N "
`
`CD
`
`~
`(.')
`
`....t-
`N
`
`"
`
`0
`
`R\
`
`>-
`<(
`3:
`wen
`I-
`<(
`(.')
`
`<.O
`N
`
`"
`
`I(cid:173)
`"0 :
`• <(
`
`(J 0: _o
`LL er
`
`Q.
`
`>-
`<(
`3:
`w<c:
`I-
`<(
`(.')
`
`<.O
`..-
`
`"
`
`....t-
`..-
`r--,.
`
`<(
`
`~
`(.')
`
`0 ..-
`r--,.
`
`N ..-"
`(cid:143)
`
`(cid:143) (cid:143)
`
`D
`
`<(
`
`_J
`
`<( z
`
`1-t
`~
`0:
`w
`I-
`
`Ex.1019
`CISCO SYSTEMS, INC. / Page 7 of 35
`
`

`

`U.S. Patent
`
`Jun.24,2003
`
`Sheet 7 of 17
`
`US 6,584,093 Bl
`
`w
`DD(cid:143) DD
`z
`0
`I
`(cid:143)(cid:143)
`DD
`a..
`c:=::=:J w
`.....J
`w
`I-
`
`N
`N
`CX)
`
`zx
`<t::lD
`.....J a..
`
`co
`N co
`
`v
`N
`r-,..
`
`lD
`~
`(.!)
`
`0
`
`g\
`
`CD
`N
`,.....
`
`>-
`<
`31:
`wm
`I-
`<
`
`(.!)
`
`I(cid:173)
`C0 a:::
`• <( 0 a::: _o
`LI- (Y
`a..
`
`N ,....
`r-,..
`
`(cid:143)
`
`(cid:143)
`
`(cid:143)
`
`D
`
`>-
`<
`31:
`CD
`,.... w<
`r-,..
`I-
`<
`(.!)
`
`v
`,....
`,.....
`
`<(
`
`~
`(.!)
`
`0 ,....
`r-,..
`
`.....J
`<
`z
`1-t
`~
`~ w
`I-
`I"'.)
`N
`
`I"'.) .
`
`I
`
`Ex.1019
`CISCO SYSTEMS, INC. / Page 8 of 35
`
`

`

`U.S. Patent
`
`Jun.24,2003
`
`Sheet 8 of 17
`
`US 6,584,093 Bl
`
`I-
`
`-
`°' a::
`• <(
`0 a::
`_o
`LL~
`Q.
`
`C
`
`(cid:143) (cid:143)
`
`D
`
`N
`N
`0)
`
`0
`
`~\
`
`v
`I")
`0)
`
`>-
`X 0::
`ow
`a::>
`Q. a::
`Q.w
`-(/)
`(/)
`
`N
`
`....
`
`0)
`
`C
`
`(cid:143) (cid:143)
`
`0
`
`N
`N
`0
`
`0
`0
`
`,-~\
`
`C
`
`(cid:143) (cid:143)
`
`D
`
`v
`N
`....
`0
`
`v
`LO
`....
`0
`
`v
`I")
`0
`,-
`
`CD
`_J
`<(
`z
`::e
`a::
`w
`I-
`
`1--4
`
`0
`I")
`0)
`
`<(
`
`- v
`
`....
`....
`
`0
`
`_J
`<(
`z
`::e
`a::
`w
`I-
`
`>-
`X 0::
`ow
`O::>
`Q. a::
`Q.w
`-(/)
`en
`
`>-
`X 0::
`ow
`a::>
`Q. a::
`Q.w
`-(/)
`en
`
`>-
`X 0::
`ow
`a::>
`Q. a::
`Q.w
`-(/)
`(/)
`
`>-
`X 0::
`ow
`a::>
`Q. a::
`Q.w
`_en
`(/)
`
`N
`,-
`0
`,-
`
`C
`
`(cid:143) (cid:143)
`
`...__ __ _, (cid:143)
`
`CD
`_J
`
`Q.<( _z
`(/)i
`a::
`w
`I-
`
`0
`N
`
`0 ....
`
`....
`
`I-
`a::
`0
`,-- <(
`0 - -LL a::
`• 0 a::
`
`Q.
`
`>-
`X 0::
`ow
`a::>
`Q. a::
`Q.w _en
`
`(/)
`
`v
`v
`0
`,-
`
`0
`,-
`
`0 ....
`
`<(
`
`_J
`
`Q. <( _z
`eni
`a::
`w
`I-
`
`Ex.1019
`CISCO SYSTEMS, INC. / Page 9 of 35
`
`

`

`U.S. Patent
`
`Jun.24,2003
`
`Sheet 9 of 17
`
`US 6,584,093 Bl
`
`N
`N .,....
`.,....
`
`D
`
`(cid:143) (cid:143)
`
`0
`
`0
`
`~\
`
`....I
`<(
`z
`.....
`~
`a::
`w
`1--
`a.
`en
`
`0
`N
`N
`.,....
`
`0
`
`..... ~\
`
`<O
`N
`N
`.,....
`
`zm
`1-- >-
`en <C
`a. 3;
`'-w
`a..1-
`..... <(
`en<.!>
`
`<O
`.,....
`.,....
`.,....
`
`z<C
`I->-
`en<(
`a. 3::
`'-w
`a. I-
`..... <(
`enc.,
`
`0
`I")
`.,....
`.,....
`
`0
`.,....
`.,....
`.,....
`
`0
`I")
`.,....
`.,....
`
`1--
`
`,... a::
`,... <(
`•
`0 a::
`_o
`LL~
`-
`a.
`
`<O
`.,....
`.,....
`
`Z>-
`I-<(
`en 3;
`a..w
`.,.... e(cid:141) <(
`' I -
`
`en<.!>
`
`0
`.,....
`,-
`.,....
`
`N
`.,....
`.,....
`.,....
`
`w
`z
`(cid:143)(cid:143) o(cid:143)(cid:143)
`0
`I
`(cid:143)(cid:143)
`(cid:143)(cid:143)
`a.
`c:::=:::=J w
`....I
`w
`1--
`
`m
`w
`z
`0
`I
`a.
`w
`....I
`w
`1--
`
`N
`N
`N
`,-
`
`1--
`Na::
`,... <(
`•
`0~
`LL a::
`a.
`
`--
`
`<(
`w
`z
`0
`I
`a.
`w
`....I
`w
`I-
`
`N
`,-.,....
`,-
`
`Ex.1019
`CISCO SYSTEMS, INC. / Page 10 of 35
`
`

`

`U.S. Patent
`
`Jun.24,2003
`
`Sheet 10 of 17
`
`US 6,584,093 Bl
`
`N
`N
`I")
`.....
`
`(cid:143)
`(cid:143) a
`
`..._ __ _. D
`
`...J
`<(
`z
`1-1
`~
`a::
`w
`I-
`t')
`N
`I")
`I
`
`I-
`Ma::
`,... <(
`
`• 0~
`
`0
`N
`I")
`
`0
`
`~\
`
`co
`N
`I")
`.....
`
`0
`.....
`I")
`.--
`
`0
`.--
`.--
`.--
`
`co
`.....
`.--.....
`
`~>-
`(/) <(
`a..3:
`'w
`a_l-
`1-1 <(
`(/) c.,
`
`-
`
`1-1
`
`LL a::
`a.
`
`<(
`w
`z
`0
`I
`0.
`w
`.....J w
`I-
`
`N
`.--
`.--
`.--
`
`Ex.1019
`CISCO SYSTEMS, INC. / Page 11 of 35
`
`

`

`i,-
`~
`
`'° ~
`b
`,I;;..
`~
`1J.
`O'I
`rJ'J.
`e
`
`'"""
`-..J
`'""" 0 ...,
`'"""
`~ ....
`=-~
`
`'JJ.
`
`~
`0
`0
`N
`~,J;..
`N
`
`~
`
`= ?
`
`=
`......
`~ ......
`~
`•
`r:JJ.
`d •
`
`~
`
`FIG.15
`
`I
`
`AS4
`
`\ TO 408*
`
`H
`
`AS3
`
`\ I ~~~3 I 1 \ I H.32~~STN I)
`
`H
`.. (
`\ I H~~~3 I )
`
`AS2
`
`•
`\
`\ I H;.~~31 )
`
`408 527 714 7 .. (
`
`CALL FOR
`
`1500
`
`/
`
`FIG.14
`
`J
`
`AS4
`
`{
`
`J
`
`AS3
`
`)
`
`J
`
`AS2
`
`\ TO 408* _
`
`H.323/PSTN
`
`GW
`
`l
`
`1462
`
`1400
`
`/
`
`~
`
`3
`
`1458
`
`( 1 · ··---, < ( I HJ23 I
`
`PX2
`
`1446
`
`PXl
`
`408 527 714 7
`
`CALL FOR
`
`Ex.1019
`CISCO SYSTEMS, INC. / Page 12 of 35
`
`

`

`i,-
`~
`
`'° ~
`b
`,I;;..
`~
`1J.
`O'I
`rJ'J.
`e
`
`'"""'
`-..J
`0 ....,
`'"""'
`N
`~ ....
`'JJ. =-
`
`~
`
`~
`0
`0
`N
`~,J;..
`N
`
`~ = ?
`
`~ =
`......
`~ ......
`~
`•
`r:JJ.
`d •
`
`\ TO 408*
`
`SIP/PSTN
`
`GW2
`
`1662 -~
`
`1700
`
`/
`
`FIG.16
`
`J
`
`AS4
`
`\ TO 408*
`
`GW
`
`1662
`
`~
`
`1600
`
`/
`
`3 I < ( I SIP /PSTN I
`l
`
`FIG.17
`
`AS4
`
`AS3
`
`~
`
`1444
`
`AS2
`
`rnTI
`~ 1658
`
`I "'" I ~
`1748
`
`1446
`
`3
`
`SIP /H .323
`
`GW1
`
`AS1
`
`408 527 714 7_
`(
`
`CALL FOR
`
`0
`
`( I PX
`
`( I --· I < ( I Px°2 I<
`
`PX1
`
`408 527 714 7
`
`CALL FOR
`
`Ex.1019
`CISCO SYSTEMS, INC. / Page 13 of 35
`
`

`

`U.S. Patent
`
`Jun.24,2003
`
`Sheet 13 of 17
`
`US 6,584,093 Bl
`
`* ro
`0 v
`0
`J-
`
`z
`J-
`V)
`a..~
`,3:
`n c.,
`N n •
`
`I
`
`* ro
`0 v
`0
`J-
`
`N
`VJ
`<(
`
`z
`J-
`VJN
`'(.!)
`a.. 3:
`a..
`1--f
`(/)
`
`_,-.
`
`C0
`~ •
`
`(J -LL
`
`Ex.1019
`CISCO SYSTEMS, INC. / Page 14 of 35
`
`

`

`U.S. Patent
`
`Jun.24,2003
`
`Sheet 14 of 17
`
`US 6,584,093 Bl
`
`* co
`0 v
`0
`I-
`
`z
`N
`co._,,... I-
`(l)N
`O'>
`,-
`'c.,
`Cl. 3:
`Cl. -(/)
`
`v
`(/)
`<(
`
`N
`
`v
`
`::::.::::
`
`~~ ~
`~ 0 ID~
`
`v
`O'>
`,-
`
`l"')X
`• a..
`I
`
`-LL
`
`a..,,,
`-x
`(/) a..
`
`N
`v
`O'>
`
`0
`
`~\
`
`0
`LO
`O'>
`,-
`
`0 v
`
`O'>
`,-
`
`Ex.1019
`CISCO SYSTEMS, INC. / Page 15 of 35
`
`

`

`i,-
`~
`
`'° ~
`b
`,I;;..
`~
`1J.
`O'I
`rJ'J.
`e
`
`'"""'
`-..J
`0 ....,
`'"""' Ul
`~ ....
`'JJ. =(cid:173)~
`
`~
`
`8
`0
`N
`~,J;..
`N
`
`~
`
`~ = ......
`~ ......
`~
`•
`r:JJ.
`d •
`
`FIG.20
`
`TO 408•
`
`AS4
`
`SIP/PSTN
`
`GW2
`
`1960
`
`2050
`
`ETBGP
`
`SIP/H.323
`
`GW1
`
`PX5
`SIP
`
`AS3
`
`/
`2000
`
`1952
`2040
`
`ITBGP
`
`1954
`
`PX3
`1942 1 SIP
`~ I AS2
`ITBGP ~ 2020
`
`1946;-E
`
`2010
`
`ETBGP
`
`AS1
`
`PX1
`H.323
`
`1940
`
`1930
`
`ETBGP
`
`2030
`
`Ex.1019
`CISCO SYSTEMS, INC. / Page 16 of 35
`
`

`

`U.S. Patent
`
`Jun.24,2003
`
`Sheet 16 of 17
`
`US 6,584,093 Bl
`
`0
`
`~\
`
`wo
`I- :c ....J
`(/)I-a:::
`~LLo
`o:t
`
`,...
`N
`
`• 0 -LL.
`
`.....
`N
`
`N
`N
`~ (/)
`c.,
`<(
`
`~ - - - -1 - - - - - - -1 ~
`(.!)
`
`.....
`
`* 0
`~ Ti
`v 1--
`0
`(/)
`I- 8
`
`Ex.1019
`CISCO SYSTEMS, INC. / Page 17 of 35
`
`

`

`U.S. Patent
`
`Jun.24,2003
`
`Sheet 17 of 17
`
`US 6,584,093 Bl
`
`(cid:143) (cid:143)
`
`(cid:143)
`
`D
`
`'-.t
`N
`N
`N
`
`CD
`~
`c.,
`
`0
`
`~\
`
`(0
`N
`N
`N
`
`>-
`<(
`3:
`wCD
`I-
`<(
`c.,
`
`.....
`N .....
`LO
`LO
`LO
`0)
`.....
`
`0)
`
`N
`N
`N
`N
`
`0
`I"')
`N
`N
`
`>-
`<(
`co
`.....
`3:
`N w<
`I-
`N
`<(
`c.,
`
`.....
`N
`'I""'"
`LO
`LO
`LO
`CX)
`0
`'-.t
`
`-LL.
`
`N
`.....
`N
`N
`
`'-.t
`.....
`N
`N
`
`<(
`
`~
`c.,
`
`0 .....
`N
`N
`
`(cid:143)
`
`(cid:143) (cid:143)
`
`D
`
`CD
`.....J
`<(
`z
`~ a::
`w
`I-
`
`1---4
`
`<(
`
`1---4
`
`.....J
`<(
`z
`~ a::
`w
`I-
`
`Ex.1019
`CISCO SYSTEMS, INC. / Page 18 of 35
`
`

`

`US 6,584,093 Bl
`
`1
`METHOD AND APPARATUS FOR
`AUTOMATIC INTER-DOMAIN ROUTING OF
`CALLS
`
`This application claims the benefit of provisional appli-
`cation No. 60/097,866, filed Aug. 25, 1998.
`
`FIELD OF THE INVENTION
`
`The present invention relates generally to call routing and,
`more particularly, to automatic routing between domains.
`
`BACKGROUND OF THE INVENTION
`
`5
`
`10
`
`2
`H.323 and SIP. The two protocols are discussed in the next
`two sections with emphasis on how they achieve multi-hop
`call routing. Then we describe how to achieve distributed
`multi-hop call routing. We also discuss the addressing
`formats used in Border Gateway Protocol (BGP) which is
`used for routing of IP data packets in the backbone of the
`Internet.
`The H.323 Architecture
`Recommendation H.323 is a standard architecture for
`multimedia conferencing (voice, video, and, data) in packet(cid:173)
`based networks that was designed by the ITU-T. H.323 has
`been successfully applied as a suite of signaling protocols
`for Internet Telephony.
`The main components involved in H.323 conferencing
`are:
`Terminals: an H.323 terminal is an endpoint capable of
`generating audio, video, and data streams or any com(cid:173)
`bination thereof.
`Gatekeepers: a gatekeeper is an H.323 entity that provides
`address resolution and controls access for all types of
`H.323 endpoints. In addition, a gatekeeper may per-
`form other services such as accounting and authenti(cid:173)
`cation.
`Multipoint Control Units (MCU): an MCU is an H.323
`endpoint which provides the capability for three or
`more terminals to participate in a multipoint confer-
`ence.
`Gateways: an H.323 gateway is an endpoint that translates
`from/to H.323 to/from another multimedia conferenc(cid:173)
`ing protocols such as H.320 (conferencing on ISDN),
`or SIP. The gateways with the most relevance to
`Internet telephony are the voice gateways which are
`H.323/PSTN gateways and which carry voice only.
`Proxies: While not part of the H.323 standard, Cisco
`provides for an H.323 proxy. It behaves like an H.323/
`H.323 gateway. Useful features of the proxy include
`quality of service (QoS), Security, and Application
`Specific Routing (ASR). ASR involves forcing multi(cid:173)
`media streams to follow specific routes path towards
`the destination).
`The main signaling protocols required to implement the
`H.323 architecture are:
`RAS: Registration, Admission, and Status. It is a UDP(cid:173)
`based protocol used for communication between H.323
`endpoints and the gatekeeper and also for inter(cid:173)
`gatekeeper communication. It is part of the H.225
`recommendation.
`Q.931: is the signaling protocol used for connection
`establishment between two endpoints. It is part of the
`H.225 recommendation.
`H.245 : is the signaling protocol responsible for call
`control between endpoints. It provides for capability
`exchange, channel and coder/decoder (codec)
`negotiation, and several other functions.
`RTP: is the protocol used for carrying the real-time media
`streams over IP networks.
`T.120: is the architecture used for sharing data between
`endpoints participating in a conference.
`A gatekeeper administers one or more H.323 zones. Calls
`60 between endpoints in the same zone typically consist of a
`single hop. On the other hand, inter-zone calls will usually
`consist of multiple hops (called legs). Some examples will
`be described below which illustrate the operation of H.323
`and the problems involved with multi-hop calls.
`FIG. 2 illustrates an example 200 of H.323 call set-up. In
`FIG. 2, a call is established directly between the terminals 12
`and 22 and therefore consists of only one hop.
`
`Internet Telephony allows telephone calls to be carried
`over an Internet protocol (IP) network either end-to-end 15
`between two telephones or computers, or as one or more
`"hops" in an end-to-end telephone call. A major objective in
`creating an internet telephony system is to reduce the cost of
`voice calls while maintaining the same quality level cur(cid:173)
`rently provided in voice networks. To achieve this objective 20
`a voice call may have to be routed over multiple hops, with
`some of these hops being in the data network while others
`are in the voice network.
`Internet telephony calls are created, managed, and torn
`down by signaling protocols. These signaling protocols, 25
`when combined with a method of routing the signaling
`messages and maintaining call state allow the actual media
`(i.e. voice) to flow in packets between the endpoints. The
`standards organizations are currently enolving two Internet
`Telephony signaling protocols: H.323 and SIP. A call routing 30
`scheme can be developed separately for each signaling
`protocol, but it is highly desirable to separate the routing
`function from other control functions of the Internet, as has
`been done for the routing of IP data packets.
`The routing of telephone calls in the public switched 35
`telephone network (PSTN) is accomplished by a combina(cid:173)
`tion of common channel signaling (CCS), such as Signaling
`System #7 (SS7), a number of translation facilities in
`elements called Service Control Points (SCPs), and static
`routing tables in elements called Service Switching Points 40
`(SSPs). While the CCS routing architecture is a reasonable
`solution for the PSTN, this architecture has a number of
`serious limitations, not the least of which is the use of static
`routing tables in the SSPs. It also suffers from poor sepa(cid:173)
`ration of the name----;,address translation function ( e.g. 800 45
`number----;,destination port) from the configuration of the
`routing machinery of the PSTN.
`Initial deployments of Internet telephony have been
`designed to be similar to the PSTN and use static routing
`tables in network endpoints, gateways, or centralized call
`control elements called gatekeepers. An example of a sim(cid:173)
`plified internet telephony system architecture 100 is shown
`in FIG. 1.
`In architecture 100, terminal 12 is connected to intranet 10 55
`which has a gatekeeper 14 which acts as a routing agent for
`intranet 10. Terminal 22 is connected to intranet 20 which
`has a gatekeeper 24 which acts as a routing agent for intranet
`20. Intranets 10 and 20 are each connected to Internet 30.
`In the configuration 100 of FIG. 1, a call is routed from
`terminal 12 to terminal 14 using the routing tables in
`gatekeepers 14 and 24. One problem with the conventional
`internet telephony system 100 has no distributed routing
`protocol to ease the maintenance and distribution of routing
`information among the elements of the system.
`As mentioned above, two Internet Telephony protocols
`are presently evolving within the standards organizations:
`
`50
`
`65
`
`Ex.1019
`CISCO SYSTEMS, INC. / Page 19 of 35
`
`

`

`US 6,584,093 Bl
`
`10
`
`25
`
`3
`However, the H.323 recommendation also defines a sig(cid:173)
`naling model for gatekeeper routed calls. In the gatekeeper
`model, the Q.931 and H.245 signaling may flow through a
`gatekeeper while the RTP media streams still flow directly
`between the terminals, as in FIG. 2. In this case, the 5
`signaling part of the call consists of two call legs: one call
`leg from terminal 12 to gatekeeper 14; and one call leg from
`gatekeeper 14 to terminal 22.
`Routing calls to H.323 terminals, or other entities, outside
`the caller's local area system requires multi-hop routing.
`Several solutions have been proposed which involve:
`manual configuration of gatekeepers; inter-gatekeeper com(cid:173)
`munication; and the use of directory servers. Most of these
`solutions consider only calls consisting of one call leg, and
`none of them scale well to large networks nor provide for
`dynamic update of call routes over time.
`An Internet Service Provider (ISP) may also wish to
`enforce certain Quality of Service ( QoS) and security poli(cid:173)
`cies on H.323 calls. To achieve this, the call may be directed
`through proxies 16 and 26, as shown in the architecture 300
`of FIG. 3.
`This call setup works as follows:
`Terminal 12 requests admission from its gatekeeper 14, to
`call Terminal 22. Admission typically includes at least:
`authorizing of the call, resolution of the destination
`address; and accounting for the call.
`Gatekeeper 14 directs Terminal 12 to connect to Proxy 16.
`Terminal 12 connects to Proxy 16.
`Proxy 16 receives the call and queries Gatekeeper 14 on
`how to forward the call.
`Gatekeeper 14 instructs Proxy 16 to connect to Proxy 26.
`Proxy 16 connects to Proxy 26.
`Proxy 26 receives the call and queries Gatekeeper 24 on
`how to forward the call.
`Gatekeeper 24 instructs Proxy 26 to connect to Terminal 35
`22.
`Proxy 26 connects to Terminal 22.
`The Q.931 and H.245 signaling for the call, as well as the
`RTP streams, all pass through the proxies 16 and 26. In the
`example of FIG. 3, the call consists of three call legs (layer
`7 hops). Cisco gatekeepers and proxies can implement a
`three-hop call, such as the one demonstrated in FIG. 3, by
`isolating the source zone, i.e. intranet 10, and the destination
`zone, i.e. intranet 20, from the rest of the network 30.
`The situation can be further complicated by decomposing
`the Internet cloud 30 of FIG. 3 into multiple ISP networks
`as shown in FIG. 4. In multiple ISP networks, each ISP can
`have different policies. Therefore each ISP places proxies at
`the border of its network and forces all incoming H.323 calls
`to go through these proxies in order to enforce its specific 50
`policies on the calls.
`In the network architecture 400 of FIG. 4, proxy 16 is
`coupled to ISP network 430 which includes gatekeeper 434.
`ISP network 430 is connected through proxy 436 to ISP
`network 440. ISP network 440 includes gatekeeper 444 and 55
`is connected to ISP 450 through proxy 446. ISP network 450
`includes gatekeeper 454 and is connected to proxy 26.
`In the example of FIG. 4, a call from Terminal 12 to
`Terminal 22 will consist of five call legs. In conventional
`internet telephony technology, there is no mechanism avail- 60
`able that can realize such a multi-hop (more than three hops)
`scenario. Once the call leaves the source zone by passing
`through proxy 16 to ISP network 430 and then on to ISP
`network 440, the application layer addressing identifying
`terminal 22 is unavailable for routing. Neither inter- 65
`gatekeeper communication nor directory services are able to
`solve this application layer routing problem.
`
`4
`Inter-gatekeeper communication and directory services
`can only resolve a layer 7 destination address into a layer 3
`address of a gateway to the layer 7 domain (e.g. the PSTN).
`Therefore, the layer 7 address, which is the actual desired
`destination, becomes irrelevant to the IP network routing
`which takes place. For instance, a layer 7 directory may have
`multiple entries for a given destination address, where each
`entry may include a gateway protocol type or gateway cost.
`However, directories are not dynamic enough to store cur(cid:173)
`rent status information for the gateway represented by each
`entry.
`For example, there may be two gateways, a primary and
`a secondary, available to reach the 408 area code through the
`internet. If the primary gateway is out of service, then 408
`15 area code is still physically accessible. However, once the
`directory resolves the layer 7 /PSTN destination address to
`the layer 3 address of the primary gateway, then the IP
`network routes only on the basis of the layer 3 address and
`not the layer 7 destination. All the IP network knows is that
`20 it can't reach the layer 3 address of the first gateway. Once
`the layer 3 address is obtained from the static directory table
`and the call is sent out into the multiple ISP network, the call
`will be dependent upon the availability of the layer 3
`address.
`Similarly, there can be multiple ISPs with gateways to a
`layer 7 domain, such as the PSTN, where some gateways are
`better than others. For example, a gateway to the 408* area
`code from an ISP in San Jose will likely be cheaper in terms
`of telephony costs than a gateway to the 408* area code from
`30 an ISP in Oakland, even though the Oakland ISP may require
`fewer IP hops and therefore be cheaper in terms of IP
`network costs.
`Therefore, the need
`application-layer routing
`inter-ISP calls.
`FIG. 5 shows an example of a call routed through a voice
`gateway 516. In order for the H.323 terminal 522 to be able
`to call a telephone 512 on PSTN 510, the gatekeeper 534
`routes the call to the appropriate gateway 516 given the
`40 telephone number of the call. However, there are likely to
`multiple gateways to the PSTN 510 through which the call
`could route. The PSTN access costs, i.e. phone charges, are
`likely to be lower through some gateways than others.
`However, the call from the H.323 terminal 522 to gateway
`45 516 will be routed by the internet 530 based upon the lowest
`internet cost, irrespective of the telephony costs involved in
`using a particular gateway.
`A static routing table of the conventional art can be
`modified to reflect the PSTN access costs of the various
`available gateways and choose the one with the lowest cost.
`Then the internet 530 will route to that gateway using BGP
`based upon the least number of hops. However, the static
`routing table solution is unable to cope with a failure of
`gateway 516 when other gateways to the same destination
`phone number are still available. The system will then drop
`the call when it is unable to reach gateway 516. In addition,
`the static routing table will also typically require a high
`degree of manual configuration to set up and maintain the
`available routes in a large network.
`In contrast, the present invention is able to route the call
`through the IP network to the appropriate gateway according
`to an aggregate cost function of both the layer 7 gateway
`cost and the IP network costs. Some possible cost functions
`are: minimize the total number of hops, minimize the
`distance traversed in the layer 7/PSTN domain, minimize
`the distance traversed in the IP data network, or minimize
`the monetary cost of the call. To make the appropriate call
`
`remains for an inter-domain
`protocol that handles multi-hop
`
`Ex.1019
`CISCO SYSTEMS, INC. / Page 20 of 35
`
`

`

`US 6,584,093 Bl
`
`25
`
`5
`routing decision, each gatekeeper also needs sufficient status
`information about the reachability of E.164 prefixes in the
`PSTN. The PSTN call leg, between the gateway and the
`telephone, is treated no differently from the call legs within
`the data network.
`Therefore, the need remains for a routing system which is
`self-configuring, routes based upon an aggregate cost of the
`call and which maintains current status information regard(cid:173)
`ing 'each route to the destination.
`Typically, the only addressing format PSTN telephones
`understand is E.164 numbers. Therefore, in order for the
`PSTN telephone 512 to be able to call the H.323 terminal
`522 through the voice gateway, the H.323 terminal 522 must
`have an E.164 number assigned to it. And the gateway 516,
`or the gatekeeper 534, must be able to route the call to the
`H.323 terminal 522 through the IP network 530 based on the
`H.323 terminal's E.164 number.
`FIG. 6 shows how a call can be established from a PSTN
`telephone 512, through voice gateway 516, onto the IP
`network 630, then through another voice gateway 626, back
`to PSTN 620 and eventually to the called telephone 622.
`Here once the call hops onto the IP network 630, the
`gateway 516, or the gatekeeper 634, must decide which hop
`off gateway to route the call to. This decision is made based
`on the called E.164 number. Note that Cisco's voice gate-
`ways can be configured to operate without gatekeepers, and
`in this case will have to make the call routing decisions on
`their own. Remember also that the IP cloud 630 of FIG. 6
`can be decomposed into multiple ISP networks similar to
`those in FIG. 4, and therefore the call leg across the IP
`network 630 may actually consist of multiple hops.
`FIG. 7 shows a voice call between two H.323 terminals
`through PSTN 730. The problem here is to provide gate(cid:173)
`keeper 714, or gateway 716, of the calling terminal's IP
`network 710 with call routing information about the called
`IP network 720. This is possible if the two IP networks 710
`and 720 are connected because they are both part of the
`overall Internet. As far as the IP network as a whole is
`concerned, the PSTN cloud 730 will be represented as just
`a link between two IP nodes, e.g. gateways 716 and 726.
`FIG. 8 shows a similar topology to FIG. 7, wherein one of
`the H.323 terminals 722 is replaced with a LAN PBX 828
`and telephone 822.
`The SIP Architecture
`The Session Initiation Protocol (SIP) is an Internet Con(cid:173)
`ferencing Protocol being developed in the IETF. SIP is a
`signaling protocol for establishing connections betw~en
`endpoints participating in a conference call. The endpomts
`advertise their capabilities and media channel information to
`other nodes in the network using the Session Description 50
`Protocol (SDP) format. These capabilities are included in the
`SIP connection establishment messages. RTP is used for
`carrying the actual media streams.
`The main components involved in SIP conferencing are:
`Terminal: a SIP entity capable of creating media streams 55
`and of participating in SIP conferences.
`Proxy Server: receives SIP requests from a client and
`creates the corresponding requests for the next call leg
`of a SIP call.
`Redirect Server: receives SIP requests from a client and 60
`responds with addressing information about where the
`call should be forwarded.
`Gateway: for example, a gateway from SIP to PSTN, from
`SIP to H.323.
`Example Topologies
`FIG. 9 shows an example of a simple SIP call through an
`architecture 900 which includes proxy server 934. The
`
`6
`caller, Terminal 912, sends a SIP request to the proxy server
`934. The proxy server 934 forwards the request to the called,
`Terminal 922. Similarly, a SIP response from Terminal 922
`goes through the proxy server 934. However, the media
`5 streams flow directly between the two endpoints 912 and
`922 through Internet 930.
`FIG. 10 illustrates another example of a SIP call in an
`architecture 1000 wherein Internet 930 is composed of
`multiple ISP networks 1030, 1040 and 1050. In FIG. 10, the
`10 signaling between the two SIP terminals 1012 and 1022
`flows through multiple proxy servers 1014, 1034, 1044,
`1054 and 1024, thus segmenting the call into multiple call
`legs. The SIP specification does not describe how to achieve
`such a multi-hop scenario. The need remains for a call-
`15 routing protocol for routing SIP calls through multiple call
`legs.
`FIG. 11 shows an example of a voice call in an architec(cid:173)
`ture 1100 which includes an SIP/PSTN gateway 1116. The
`call originates from a PSTN telephone 1112 in PSTN 1110,
`20 connects to SIP/PSTN voice gateway 1116 which routes the
`call through Internet 1130 to a SIP terminal 1122. The same
`call routing issues apply to this scenario as were discussed
`above with regard to FIG. 5 for calls between a PSTN
`telephone and an H.323 terminal.
`FIG. 12 shows an example of a toll bypass call in an
`architecture 1200 involving two voice gateways 1116 and
`1226. The call between two PSTN telephones 1112 and 1222
`hops of PSTN 1110 onto the IP network 1130 through
`gateway 1116 and back onto the PSTN 1220 through gate-
`30 way 1226. The PSTNs 1110 and 1220 are different parts of
`the overall PSTN, but the call has bypassed long-distance
`toll charges by passing from one local zone I I 10 of the
`PSTN through the IP network 1130 to another local zone
`1220 of the PSTN. In this case SIP is the protocol used to
`35 carry t