Method and apparatus for automatic inter-domain routing of calls

• US 6,584,093 B1
• Filed: 01/05/1999
• Issued: 06/24/2003
• Est. Priority Date: 08/25/1998
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Salama, Hussein Farouk, Oran, David R., Shah, Dhaval N.
• Primary Examiner(s): Hsu, Alpus H.
• Assistant Examiner(s): TRAN, THIEN D
• Application Number:
  US09/225,921
• Time in Patent Office: 1,631 Days
• Field of Search: 370/238.1, 370/465, 370/466, 370/467, 370/469, 370/389, 370/392, 370/351, 370/352, 370/353, 370/354, 370/355, 370/356
• US Class Current: 370/351
• CPC Class Codes: H04L 12/2856 Access arrangements, e.g. Internet access asynchronous transfer mode networks H04L12/5601; broadband local area networks H04L12/2801; optical access or distribution networks H04Q11/0067; access to open networks H04L12/5691; digital subscriber line end-user equipment and bit-level processing of data on a PSTN-based network H04M11/00; home network gateways H04L12/2834; wireless access networks H04W
• CPC Class Codes: H04L 12/2898 Subscriber equipments DSL modems H04M11/062; cable modems H04L12/2801
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/033 by updating distance vector protocols
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 65/1101 Session protocols
• CPC Class Codes: H04L 65/1104 Session initiation protocol [SIP]
• CPC Class Codes: H04L 65/1106 Call signalling protocols; H.323 and related
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: H04M 7/1285 Details of finding and selecting a gateway for a particular call

Abstract

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.

Claims

1. A routing node operable for inter-domain call routing, comprising:

a memory to store a routing table;

a call routing processor to communicate with the memory and to communicate with a network;

the call routing processor operable to;

receive a call routing update message from another node of the network, the message to comprise a network address to an adjacent entity of the network, an aggregation of application addresses which the adjacent entity can access and respective cost value,

responsive to receiving the call routing update message, the call routing processor further operable to;

write the routing table of the memory to associate the network address for the adjacent entity, the aggregation of application addresses which the adjacent entity can access and the respective cost value,

establish a modified call routing update message comprising a network address of the routing node, the aggregation of application addresses which the adjacent entity can access, and an incremented cost value related to an incrementing of the cost value of the received call routing update message, and

forward the modified call routing update message to all adjacent entities; and

another routing table;

for each value that is associated with the range of application addresses which the adjacent entity can access of the entries in the routing table, the call routing processor further operable to

determine all entries in the call routing table having the same value for the range of application addresses which the adjacent entity can access,

select one of the determined entries of the same value for the range of application addresses which the adjacent entity can access, the selection to depend on the relative cost of the determined entries, and

insert the selected one of the determined entries of lowest cost value into the another routing table;

the call routing processor further operable to;

receive a call having a destination address;

responsive to receiving the call, search the another routing table for an entry where the destination address of the call is within the range of addresses which the adjacent entity can access; and

route the call to the adjacent entity of the network address of the entry of the another routing table that comprises the range of addresses encompassing the destination address.

2. The routing node of claim 1, the call routing processor further operable to:

receive the call routing update message, which may comprise a protocol type of the adjacent entity;

include the protocol type in the routing table in association with the entry created responsive to the call routing update message; and

preference entries of a first protocol type over entries of a second protocol type during the selection and insertion of the entry into the another routing table.

3. A method of inter-domain call routing, the method comprising:

receiving a call routing update message comprising a network address for an adjacent node in a network, a range of application addresses which the adjacent node can access and an aggregate cost value for access to the range of application addresses through the adjacent node;

writing an entry in a routing table responsive to receiving the call routing update message, the entry to associate the network address for the adjacent node, the range of application addresses which the adjacent node can access and aggregate cost value for access to the range of application addresses through the adjacent node;

modifying the call routing update message and forming a modified routing update message comprising a network address for the routing node of the updated routing table, the range of application addresses which the adjacent node can access and an incremented cost value obtained by incrementing the aggregate cost value of the initial call routing update message;

forwarding the modified call routing update message to adjacent nodes;

for each value of the range of addresses which the adjacent node can access from the routing node;

searching the routing table and determining entries having the same value,

selecting one of the determined entries based on their relative cost value, and

writing another routing table with information of the selected entry;

receiving a call having a destination address;

searching the another routing table and determining entries thereof having a range of

addresses that include the destination address of the call received; and

routing the call to an adjacent node of a network address corresponding to that of the entry associated with and determined to have the range of addresses that include the destination address of the received call.

4. The method of claim 3, in which:

the receiving a call routing update message comprises receiving and determining a protocol type supported by the adjacent node;

the inserting an entry in a routing table comprises associating the determined protocol type within the entry; and

the selecting one of the determined entries is further dependent on the protocol type of the respective entries.

5. A self-configuring inter-domain call routing system, the system comprising:

a plurality of autonomous systems (ASes);

at least one AS comprising a routing agent;

each routing agent to;

store a routing table,

receive a first call routing update message comprising a first network address value of an entity in an adjacent AS, a range of second network addresses accessible by the entity in the adjacent AS and respective cost value, and

responsive to receiving the first call routing update message, to;

place an entry into the routing table to associate the first network address value, the range of second network addresses and the respective cost value of the first call routing update message,

modify the first call routing update message by incrementing the cost value and replacing the first network address of the entity in the adjacent AS with its own first network address;

each routing agent further to forward the modified first routing update message to the routing agents of adjacent ASes, and

responsive to receiving a call to a second network destination address, the routing agent further to;

search its routing table and determine entries that identify access to the second network destination address,

select one of the determined entries of lowest relative cost value, and

route the call to the routing agent of the first network address associated within the selected entry.

6. The inter-domain call routing system of claim 5, each routing agent further operable to:

receive a second call routing update message comprising a first network address value of an entity in an adjacent AS and a range of second network addresses, and

responsive to receiving the second call routing update message, mark as unavailable an entry in its routing table associated with the first network address value and the range of second network addresses of the second call routing update message,

modify the second call routing update message by replacing the first network address value with its own, and

transmit the modified second call routing update message to routing agents of adjacent ASes.

7. The inter-domain call routing system of claim 6, in which:

a first AS of the plurality of ASes comprises a gateway,

the gateway operable to;

access a first set of second network addresses, and

transmit the first routing update message to the routing agent of the first AS, the first routing update message to comprise a first network address of the gateway, the first set of second network addresses and respective cost value.

8. The inter-domain call routing system of claim 7, responsive to loss of access to the first set of second network addresses, the gateway further operable to transmit to the routing agent of the first AS, the second call routing update message comprising the first network address of the gateway and the first set of second network addresses.

9. The inter-domain call routing system of claim 8, in which the first network addresses to comprise layer 3 addresses and the first set of second network addresses to comprise layer 7 addresses.

10. The inter-domain call routing system of claim 9, in which the first network addresses to comprise IP addresses and the first set of second network addresses to comprise H.323 addresses.

11. The inter-domain call routing system of claim 10, the cost value of the first routing update message from the gateway to comprise the aggregate cost for access to the layer 7 addresses.

12. The inter-domain call routing system of claim 8, in which the plurality of ASes comprises part of a first wide area network and the gateway comprises an interface to a second wide area network.

13. The inter-domain call routing system of claim 12, in which the plurality of ASes comprises an IP network and the gateway.comprises an interface to a public switched telephone network (PSTN).

14. The inter-domain call routing system of claim 13, the cost value associated with the first call routing update message from the gateway to comprise an aggregate of costs of intermediate hops of the network together with the cost for access to the PSTN.

15. The inter-domain call routing system of claim 6, the first call routing update message to further comprise a protocol type,

the routing agent further operable to:

associate the protocol type of the first call routing update message with the entry created responsive to the first call routing update message; and

responsive to receiving a call to a second network destination address, to;

search its routing table and determine entries comprising addresses matching the second network destination address of the received call and protocol type matching that of the call,

select one of the determined entries based on its relative cost value, and route the received call to the routing agent of the first network address corresponding to that associated within the selected entry.

16. The inter-domain call routing system of claim 15, in which:

the gateway is operable to process calls having a first protocol type value;

the second AS comprises;

a proxy entity to convert calls between the first protocol type and a second protocol type,

the proxy entity to transmit first and second ones of the first call routing update message,

the first one to comprise a first network address of the proxy entity, a range of second network addresses and the first protocol type,

the second one to comprise the first network address of the proxy entity, the range of second network addresses and the second protocol type; and

responsive to a call having the second protocol type, the routing agent of the second AS operable to route the call of the second protocol type to the proxy entity.

17. The inter-domain call routing system of claim 5, in which, for at least one value of the range of second network addresses that the entity in the adjacent AS can access of the routing table, the routing agent is further operable to:

search the routing table and determine entries thereof having the same value,

select a first one of the determined entries based on its associated cost value, and

insert the select entry into another routing table; and

responsive to receiving the call of the second network destination address, the routing agent further to;

search the another table and find an entry thereof that identifies access to the second network destination address, and

route the call to the routing agent of the first network address corresponding to that associated within the entry found in the another table to identify access to the second network destination address.

18. The inter-domain call routing system of claim 17, in which:

the routing agent is further operable to receive a second call routing update message comprising a first network address of an entity in an adjacent AS and a range of second network addresses;

responsive to receiving the second call routing update message, the routing agent further to;

mark as unavailable the entry in its routing table that matches the first network address of the second call routing update message,

modify the second call routing update message by replacing the first network address value with its own first network address,

transmit the modified second call routing update message to the routing agents of adjacent Ases, and

determine if the another routing table includes an entry corresponding to the entry of the routing table marked as unavailable;

if the determining identifies such corresponding entry, the routing agent further operable to;

search its routing table and determine entries thereof other than the previously selected one of value corresponding to that of the at least one value of the range of second network addresses which the entity in the adjacent AS can access,

select a second one of the secondly determined entries based on their associated cost value, and

insert the second select entry into the another routing table.

29. The routing system of claims 17, the routing agent further operable to make the selection of the first one of the determined entries based on which entry comprises the lowest relative cost.

19. An inter-domain call routing system comprising:

a plurality of autonomous systems (ASes),

each AS being coupled to at least one other AS of the plurality,

at least one AS comprising a routing agent with a routing table;

a first AS of the plurality of ASes comprising a gateway operable to access a first set of addresses, and

a second AS of the plurality of ASes disposed adjacent the first AS;

the gateway further operable to;

send a first message to the routing agent of the first AS,

the first message to identifying an address of the gateway, access to the first set of addresses and respective cost value;

responsive to the first message, the routing agent of the first AS operable to;

insert an entry into its routing table to associate the address of the gateway, access to the first set of addresses and the respective cost value,

form a second message by incrementing the cost value of the first message, and

send the second message to the routing agents of ASes adjacent to the first AS,

the second message to identify an address of the routing agent of the first AS, access to the first set of addresses and the incremented cost value;

responsive to the second message, the routing agent of the second AS operable to;

insert an entry into its routing table to associate the address of the routing agent of the first AS, access to the first set of addresses and the associated cost value,

form a third message by incrementing the cost value of the second message, and

send a third message to the routing agents of ASes adjacent to the second AS,

the third message to identify an address of the routing agent of the second AS, access to the first set of addresses and the additionally incremented cost value; and

responsive to receiving a call addressed to one of the first set of addresses, the at least one routing agent further operable to;

search its routing table and determine entries thereof that identify access to the first set of addresses, and

route the call to a routing agent associated with one of such determined entries of lowest relative cost value.

20. The inter-domain call routing system of claim 19, in which:

the plurality of ASes form at least part of a first wide area network; and

the gateway is an interface to a second wide area network; and

the first set of addresses to correspond to destinations in the second wide area network.

21. The inter-domain call routing system of claim 20, which the first wide area network is an Internet protocol (IP) network and the second wide area network is a public switched telephone network (PSTN).

22. The inter-domain call routing system of claim 21, in which the cost value for access to the first set of addresses through the gateway to correspond to telephony costs to access the PSTN through the gateway.

23. The inter-domain call routing system of claim 19, in which the addresses of the gateway and the routing agents in each AS to comprise layer 3 addresses and the first set of addresses to comprise layer 7 addresses.

24. The inter-domain call routing system of claim 19, in which:

the routing agent of the first AS is further operable, responsive to loss of access to the first set of addresses through the gateway, to transmit a fourth message comprising the address of the routing agent of the first AS and a notice of such loss of access to the first set of addresses;

responsive to the fourth message, the routing agent of the second AS further operable to;

mark as unavailable an entry in its routing table associated with the address of the routing agent of the first AS, and

forward the fourth message to ASes adjacent to the second AS.

25. The inter-domain call routing system of claim 19, in which:

the gateway is further operable to process calls having a first protocol and the first message to include an identifier for the first protocol;

the entry in the routing table of the routing agent of the second AS to further associate therewith the identifier for the first protocol; and

responsive to receiving a call that is addressed to one of the first set of addresses and of the first protocol, the at least one routing agent further operable to;

search its routing table and determine entries identifying access to the first set of addresses and identification for the first protocol, and

route the call to the routing agent of address corresponding to that within a select one of the determined entries of the lowest relative cost.

26. The inter-domain call routing system of claim 25, in which:

the first AS further comprises a proxy operable to process calls having a second protocol;

the routing agent of the first AS further operable to send out a fifth message to identify an address of the proxy, access to the first set of addresses and the respective cost value;

the second routing agent of the second AS further operable, responsive to the fifth message, to insert an entry in its routing table to associate the address of the proxy of the first AS, access to the first set of addresses, the cost value and an identifier for the second protocol;

the second routing agent to forward the fifth message to ASes adjacent the second AS; and

responsive to receiving a call addressed to one of the first set of addresses of the second protocol, the at least one routing agent further operable to;

search its routing table and determine entries identifying access to the first set of addresses and the second protocol, and

route the call to the routing agent associated with one of the determined entries of lowest cost value.

27. The inter-domain call routing system of claim 19, where:

each routing agent is further operable to;

search its routing table and determine all entries indicating access to the first set of addresses,

select the entry of the lowest cost value from amongst the determined entries, and

write another routing table with data of the selected entry; and

responsive to receiving a call addressed to one of the first set of addresses, each routing agent further operable to;

search the another routing table to determine an entry thereof identifying access to the first set of addresses, and

route the call to the routing agent of address corresponding to that associated within the determined entry.

28. The inter-domain call routing system of claim 27, where:

responsive to losing access to the first set of addresses through the gateway, the routing agent of the first AS is further operable to transmit a fourth message comprising the address of the routing agent of the first AS and notice of loss of access to the first set of addresses;

responsive to receipt of the fourth message, the routing agent of the second AS further operable to;

mark as unavailable the entry in its routing table that associates the address of the routing agent of the first AS with the first set of addresses,

forward the fourth message to ASes adjacent to the second AS, and

replace the corresponding entry in the another routing table with another entry of the routing table that is associated with the first set of addresses and of the next lowest relative cost.