of 17
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

(12) Patent Application Publication (10) Pub. No.: US 2007/ A1

Category:

Philosophy

Publish on:

Views: 3 | Pages: 17

Extension: PDF | Download: 0

Share
Description
(19) United States (12) Patent Application Publication (10) Pub. No.: US 2007/ A1 Previdi et al. (54) TECHNIQUE FOR OPTIMIZED ROUTING OF DATA STREAMS ON AN IPBACKBONE IN A COMPUTER NETWORK (76)
Transcript
(19) United States (12) Patent Application Publication (10) Pub. No.: US 2007/ A1 Previdi et al. (54) TECHNIQUE FOR OPTIMIZED ROUTING OF DATA STREAMS ON AN IPBACKBONE IN A COMPUTER NETWORK (76) Inventors: Stefano B. Previdi, Rome (IT): David D. Ward, Los Gatos, CA (US) Correspondence Address: CESAR AND MCKENNA, LLP 88 BLACK FALCON AVENUE BOSTON, MA US A1 (43) Pub. Date: Sep. 6, 2007 Publication Classification (51) Int. Cl. G06F 5/73 ( ) (52) U.S. Cl /238 (57) ABSTRACT A technique optimizes routing of application data streams on an Internet Protocol (IP) backbone in a computer network. According to the novel technique, a client router learns of server states (e.g., number of pending requests, etc.) of a plurality of application servers and also determines metrics of intermediate links between the application servers and the (21) Appl. No.: 11/449,162 client router (intermediate link metrics), e.g., particularly link metrics in a direction from the application servers to the (22) Filed: Jun. 8, 2006 client router. Upon receiving an application request from an 9 application client ( client request'), the client router deter O O mines to which of the application servers the client request (30) Foreign Application Priority Data is to be sent based on the server states and intermediate link Mar. 1, 2006 (IT)... TO2OO6AOOO149 metrics, and sends the client request accordingly. APPLICATION CLIENT APPLICATION RECUESTS CLIENT ROUTER APPLICATION DATA STREAMS INTERMEDIATE ROUTERA u-e- ROUTER SERVER 1 INTERMEDIATE NETWORK (LAN/WAN) APPLICATION DATASTREAMS d INTERMEDIATE ROUTERB SERVER ROUTER2 Patent Application Publication US 2007/ A1 ELWIGE WHELNI Patent Application Publication Sep. 6, 2007 Sheet 2 of 8 US 2007/ A1?ŽZ AHOWEN Patent Application Publication Sep. 6, 2007 Sheet 3 of 8 US 2007/ A1 1. IGPADVERTISEMENT 300 INTRA-DOMAIN ROUTING PROTOCOL DISCRIMINATOR 302 LENGTH INDICATOR 304 VERSION PROTOCOLIDEXT 306 RESERVED 308 TYPE 310 VERSION 312 ECO 314 USERECO 316 PDULENGTH 318 SOURCE ID 320 OTHERTYPE-SPECIFICFIELDS 322 VARIABLE LENGTH FIELDS (TLVs) DATA 500 SECTION FIG. 3 Patent Application Publication Sep. 6, 2007 Sheet 4 of 8 US 2007/ A1 CLIENT APPLICATION REQUES COMMON HEADER 410 SOURCE ADDRESS DESTINATION ADDRESS APPLICATION REOUEST FIELDS 1 INFORMATION 420 FIG. 4 Patent Application Publication Sep. 6, 2007 Sheet 5 of 8 US 2007/ A1 -VARIABLE LENGTH FIELD 500 TYPE 505 LENGTH 510 VALUE 515 SERVER ID 520 TYPE 555 LENGTH 560 SUB-TLV(S) 550 VALUE 565 FIG. 5 Patent Application Publication Sep. 6, 2007 Sheet 6 of 8 US 2007/ A1 NOIIVOIddy 009?IGVI HHAHES Patent Application Publication Sep. 6, 2007 Sheet 7 of 8 US 2007/ A1 / SO - Patent Application Publication Sep. 6, 2007 Sheet 8 of 8 US 2007/ A1 START ) SERVER ROUTERS MAINTAIN SERVER IDS AND SERVER STATES OF APPLICATION SERVERS 810 SERVER ROUTERS PROPAGATE SERVER IDS AND SERVER STATES INTO THENETWORK, e.g., USINGIGPADVERTISEMENTS 815 INTERMEDIATE ROUTERS PROPAGATE LINK METRICS INTO THENETWORK, e.g., USINGIGPADVERTISEMENTS 820 CLIENT ROUTER RECEIVES IGPADVERTISEMENTS (e.g., LEARNING THE INFORMATION) 825 CLIENT ROUTER STORES SERVERDS AND SERVER STATES IN APPLICATION SERVERTABLE 830 CLIENT ROUTER COMPUTES REVERSE SPT FROM ITSELF TO EACH APPLICATIONSERVERBASED ONLINKMETRICS INADIRECTION TOWARDITSELF 835 CLIENT ROUTER RECEIVES CLIENT REQUEST (e.g., INTERCEPTINGREQUESTORACTING ASAPPLICATIONSERVER PROXY)840 CLIENTROUTER DETERMINESTOWHICHAPPLICATIONSERVER THE REQUEST ISTOBESENTBASEDONSERVERSTATES AND LINKMETRICSOFREVERSE SPTs 845 NO NEED TO MODIFY APPLICATION SERVERDESTINATION? CLIENTROUTER MODIFIES CLIENT REQUEST DESTINATION OR REPLY TO APPLICATIONCLIENT WITHCORRESPONDINGAPPLICATIONSERVERDESTINATION CLIENT ROUTER FORWARDS CLIENT REQUEST 860 FIG. 8 C END D-865 US 2007/ A1 Sep. 6, 2007 TECHNIQUE FOR OPTIMIZED ROUTING OF DATA STREAMS ON AN IPBACKBONE IN A COMPUTER NETWORK CROSS REFERENCE TO RELATED APPLICATIONS This Application claims the priority benefit of Italian Patent Application No. TO2006A000149, filed Mar. 1, 2006, by Stefano B. Previdi, et al., entitled TECNICA PER LINSTRADAMENTO OTTIMIZZATO DI FLUSSI DI DATI SU UNA DORSALE IP IN UNA RETE DI COMPUTER, the contents of which are hereby incorporated by reference in their entirety. BACKGROUND OF THE INVENTION Field of the Invention The present invention relates to computer networks and more particularly optimizing routing of application data streams on an Internet Protocol (IP) backbone in a computer network Background Information A computer network is a geographically distributed collection of nodes interconnected by communication links and segments for transporting data between end nodes, such as personal computers and workstations. Many types of networks are available, with the types ranging from local area networks (LANs) to wide area networks (WANs). LANs typically connect the nodes over dedicated private communications links located in the same general physical location, such as a building or campus. WANs, on the other hand, typically connect geographically dispersed nodes over long-distance communications links, such as common car rier telephone lines, optical lightpaths, synchronous optical networks (SONET), or synchronous digital hierarchy (SDH) links. The Internet is an example of a WAN that connects disparate networks throughout the world, providing global communication between nodes on various networks. The nodes typically communicate over the network by exchang ing discrete frames or packets of data according to pre defined protocols, such as the Transmission Control Proto col/internet Protocol (TCP/IP). In this context, a protocol consists of a set of rules defining how the nodes interact with each other. Computer networks may be further intercon nected by an intermediate network node, such as a router, to extend the effective size' of each network Since management of interconnected computer networks can prove burdensome, Smaller groups of com puter networks may be maintained as routing domains or autonomous systems. The networks within an autonomous system (AS) are typically coupled together by conventional intradomain routers configured to execute intradomain routing protocols, and are generally Subject to a common authority. To improve routing scalability, a service provider (e.g., an ISP) may divide an AS into multiple areas or levels. It may be desirable, however, to increase the number of nodes capable of exchanging data; in this case, interdomain routers executing interdomain routing protocols are used to interconnect nodes of the various ASes. More over, it may be desirable to interconnect various ASes that are operated under different administrative domains. As used herein, an area or level, or more particularly, an AS, is generally referred to as a domain Examples of an intradomain routing protocol, or an interior gateway protocol (IGP), are the Open Shortest Path First (OSPF) routing protocol and the Intermediate-System to-intermediate-system (IS-IS) routing protocol. The OSPF and IS-IS protocols are based on link-state technology and, therefore, are commonly referred to as link-state routing protocols. Link-state protocols define the manner with which routing information and network-topology informa tion are exchanged and processed in a domain. This infor mation is generally directed to an intradomain router's local state (e.g., the routers usable interfaces and reachable neighbors or adjacencies). The OSPF protocol is described in RFC 2328, entitled OSPF Version 2, dated April 1998 and the IS-IS protocol used in the context of IP is described in RFC 1195, entitled Use of OSI IS-IS for routing in TCP/IP and Dual Environments, dated December 1990, both of which are hereby incorporated by reference An intermediate network node often stores its routing information in a routing table maintained and man aged by a routing information base (RIB). The routing table is a searchable data structure in which network addresses are mapped to their associated routing information. However, those skilled in the art will understand that the routing table need not be organized as a table, and alternatively may be another type of searchable data structure. Although the intermediate network node's routing table may be config ured with a predetermined set of routing information, the node also may dynamically acquire ( learn') network rout ing information as it sends and receives data packets. When a packet is received at the intermediate network node, the packet's destination address may be used to identify a routing table entry containing routing information associ ated with the received packet. Among other things, the packet's routing information indicates the packet's next-hop address To ensure that its routing table contains up-to-date routing information, the intermediate network node may cooperate with other intermediate nodes to disseminate routing information representative of the current network topology. For example, Suppose the intermediate network node detects that one of its neighboring nodes (i.e., adjacent network nodes) becomes unavailable, e.g., due to a link failure or the neighboring node going off-line, etc. In this situation, the intermediate network node can update the routing information stored in its routing table to ensure that data packets are not routed to the unavailable network node. Furthermore, the intermediate node also may communicate this change in network topology to the other intermediate network nodes so they, too, can update their local routing tables and bypass the unavailable node. In this manner, each of the intermediate network nodes becomes aware' of the change in topology Typically, routing information is disseminated among the intermediate network nodes in accordance with a predetermined network communication protocol. Such as a link-state protocol (e.g., IS-IS, or OSPF). Conventional link-state protocols use link-state advertisements or link state packets (or IGP advertisements') for exchanging routing information between interconnected intermediate network nodes (IGP nodes). As used herein, an IGP adver tisement generally describes any message used by an IGP routing protocol for communicating routing information among interconnected IGP nodes, i.e., routers and Switches. Operationally, a first IGP node may generate an IGP adver US 2007/ A1 Sep. 6, 2007 tisement and flood (i.e., transmit) the packet over each of its network interfaces coupled to other IGP nodes. Thereaf ter, a second IGP node may receive the flooded IGP adver tisement and update its routing table based on routing information contained in the received IGP advertisement. Next, the second IGP node may flood the received IGP advertisement over each of its network interfaces, except for the interface at which the IGPAdvertisement was received. This flooding process may be repeated until each intercon nected IGP node has received the IGP advertisement and updated its local routing table In practice, each IGP node typically generates and disseminates an IGP advertisement whose routing informa tion includes a list of the intermediate node's neighboring network nodes and one or more cost values associated with each neighbor. As used is herein, a cost value associated with a neighboring node is an arbitrary metric (a link metric') used to determine the relative ease/burden of com municating with that node. For instance, the cost value may be measured in terms of the number of hops required to reach the neighboring node, the average time for a packet to reach the neighboring node, the amount of network traffic or available bandwidth over a communication link coupled to the neighboring node, etc. Notably, as those skilled in the art will understand, Traffic Engineering (TE) extensions to IGP advertisements may be used to convey various link metrics, Such as, e.g., link utilization, etc. Examples of TE extensions for IGP can be found in RFC 3784 entitled Intermediate System-to-Intermediate-System (IS-IS) Extensions for Traffic Engineering (TE) dated June 2004, and RFC 3630, entitled Traffic Engineering (TE) Extensions to OSPF Version 2 dated September 2003, the contents of both of which are hereby incorporated by reference in their entirety As noted, IGP advertisements are usually flooded until each intermediate network IGP node has received an IGP advertisement from each of the other interconnected intermediate nodes. Then, each of the IGP nodes (e.g., in a link-state protocol) can construct the same view of the network topology by aggregating the received lists of neigh boring nodes and cost values. To that end, each IGP node may input this received routing information to a 'shortest path first (SPF) calculation that determines the lowest-cost network paths that couple the intermediate node with each of the other network nodes, i.e., thus computing a 'shortest path tree' (SPT), as will be understood by those skilled in the art. For example, the Dijkstra algorithm is a conventional technique for performing such an SPF calculation, as described in more detail in Section of the textbook Interconnections Second Edition, by Radia Perlman, pub lished September 1999, which is hereby incorporated by reference as though fully set forth herein. Each IGP node updates the routing information stored in its local routing table based on the results of its SPF calculation. More specifically, the RIB updates the routing table to correlate destination nodes with next-hop interfaces associated with the lowest-cost paths to reach those nodes, as determined by the SPF calculation The data packets transferred among the network nodes may include fixed-sized data cells and/or variable sized data frames. Each data packet typically comprises pay-load data prepended ( encapsulated') by at least one network header formatted in accordance with a network communication protocol. The network headers include information that enables the client nodes and intermediate nodes to route the packet efficiently through the computer network. Often, a packet's network headers include at least a datalink (layer 2) header and an internetwork (layer 3) header, as defined by the Open Systems Interconnection (OSI) Reference Model. The OSI Reference Model is gen erally described in more detail in Section 1.1 of the reference book entitled Interconnections Second Edition, by Radia Perlman, published September 1999, which is hereby incor porated by reference as though fully set forth herein In operation, a client node may send a data packet to a network interface of an intermediate network node. Thereafter, the intermediate network node receives the packet and forwards the packet to its next destination. For example, the intermediate network node may perform a layer-2 Switching function that simply re-directs the packet from one network interface to another based on the contents of the packet's data-link header. Alternatively, the interme diate network node may perform a layer-3 routing function, or forwarding decision, that selects the most appropriate network interface to forward the packet based on the con tents of the packets internetwork header Data packets are used to transport many forms of information over networks and Subnetworks. For instance, Video information may be transmitted in accordance with Video on Demand (VoID) standards known to those skilled in the art. VoD refers to a group of technologies used to transmit video information over data networks from a source node (e.g., a VoD application server) to a destination node (e.g., a VoD application client). The Source and destination nodes employ voice agents that convert video information from its traditional form to a form that is suitable for packet transmission. In other words, the source node's video agent encodes, compresses, and encapsulates the video informa tion into a plurality of data packets, and the destination node's voice agent performs complementary functions to de-encapsulate, uncompress, and decode the VoD packets. For instance, a VoD content server may supply video data streams to one or more set-top-boxes of users. Also, music information may be transmitted in accordance with stan dards known to those skilled in the art in a similar manner to VoD. Examples of music agents may include personal computers (PCs) running music applications (e.g., Apple(R) Corporation's itunes(r music program), network devices providing music services (e.g., Internet jukeboxes), etc. Notably, the use of VoID and music services are examples of applications (e.g., at an application layer) that a node within the network may operate. Those skilled in the art will understand that other applications may also be operated at network nodes A source node (sender) may be configured to transfer a unidirectional stream of data packets, or a data flow, to a destination node (receiver) in a data network. The data stream may comprise, for example, data or video/music information. The data stream is unidirectional in that data travels one-way from the sender to the receiver. The logical procession of intermediate network nodes that transmit and receive data packets from the sender to the receiver defines the data stream's data path. A first node that is nearer the receiver in the data stream's data path than a second node in the stream is said to be downstream from the second node. Likewise, a first node that is nearer the sender in the data stream's path than a second node in the stream is said to be upstream from the second node. US 2007/ A1 Sep. 6, Generally, in today s network configurations, mul tiple application content servers (e.g., VoD, music, etc.) may be dispersed throughout different parts of the network in order to ensure redundancy of the data and to provide load balancing/sharing of requests from application clients. Nota bly, though, when using standard IP routing within the network (e.g., an IP backbone'), there is no communication between the routing layer and the application layer to provide for efficient load balancing. This often creates an inconsistency in algorithms used by the application layer to attempt to load balance client requests to the multiple application servers For example, a VoD client may request a video data stream from a VoID server, which has been selected by the VoD application of the client. However, the VoD application of the client is not aware of the network resources that are utilized by the data stream from the selected server (e.g., the links/nodes the video stream would traverse from the server to the client). Because of this, any attempts to load balance client requests by the application layer are inefficient with out knowledge of the network resources and their current state, particularly when utilizing an IP backbone. Further, because the routing layer is not aware of the application requests or the state of the application servers; any attempts to load balance client requests by the routing layer are also inefficient. There remains a need, therefore, for an efficient technique that optimizes routing of application data streams on an IP backbone based on both application layer infor mation and routing layer information. SUMMARY OF THE INVENTION The present invention is directed to a technique for optimizing routing of application data streams on an Internet Protocol (IP) backbone in a computer network. According to the novel technique, a client router learns of server States (e.g., number of pending requests, etc.) of a plurality of application servers and also determines metrics of interme diate links between the application servers and the client router (intermediate link metrics), e.g., particularly link metrics in a direction from the application servers to the client router. Upon receiving an application request from an application client ( client request'), the client router deter mines to which of the application servers the client request is to be sent based on the ser
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks