2 INTRODUCTION 1.1 ARCHITECTURE OF THE INTERNET:PRESENT AND FUTURE 1.1.1 The Present Today's Internet is an amalgamation of thousands of commercial and service provider net- works.It is not feasible for a single service provider to connect two distant nodes on the Internet.Therefore,service providers often rely on each other to connect the dots.Depend- ing on the size of network they operate,Internet Service Providers(ISPs)can be broken down into three major categories.Tier-1 ISPs are about a dozen major telecommunication companies,such as UUNet,Sprint,Qwest,XO Network,and AT&T,whose high-speed global networks form the Internet backbone.Tier-1 ISPs do not buy network capacity from other providers;instead,they sell or lease access to their backbone resource to smaller Tier-2 ISPs,such as America Online and Broadwing.Tier-3 ISPs are typically regional service providers such as Verizon and RCN through whom most enterprises connect to the Internet.Figure 1.1 illustrates the architecture of a typical Tier-1 ISP network. Each Tier-1 ISP operates multiple IP/MPLS(multi-protocol label switching),and some- times ATM(asynchronous transfer mode),backbones with speeds varying anywhere from T3 to OC-192 (optical carrier level 192,~10Gbps).These backbones are interconnected through peering agreements between ISPs to form the Internet backbone.The backbone is designed to transfer large volumes of traffic as quickly as possible between networks. Enterprise networks are often linked to the rest of the Internet via a variety of links,any- where from a TI to multiple OC-3 lines,using a variety of Layer 2 protocols,such as Gigabit Ethernet,frame relay,and so on.These enterprise networks are then overhauled into service provider networks through edge routers.An edge router can aggregate links from multiple enterprises.Edge routers are interconnected in a pool,usually at a Point of Presence(POP) San Francisco Oadland Sae Jose 腰Fremon Hong Kong ■Los Angeles- ■ong8eah Oronge County ■5nDw39 LEGENO OC-12 Mariet Uplinks 一Daa CerterIP0心zwrt。CoreP Node Class 5Volce Switch Local'Voice Fooprint 一 厚FeodWeele Private Puering IP Node Lenghaul Terminacion o XD Market OC12 Basbene Cirout Pubic Poering PNde-Privats Line Babona Nwork Maigmmsrt Carts A Data Certor Figure 1.1 Network map of a Tier-1 ISP.XO Network
Book1099 — “c01” — 2007/2/16 — 18:26 — page 2 — #2 2 INTRODUCTION 1.1 ARCHITECTURE OF THE INTERNET: PRESENT AND FUTURE 1.1.1 The Present Today’s Internet is an amalgamation of thousands of commercial and service provider networks. It is not feasible for a single service provider to connect two distant nodes on the Internet. Therefore, service providers often rely on each other to connect the dots. Depending on the size of network they operate, Internet Service Providers (ISPs) can be broken down into three major categories. Tier-1 ISPs are about a dozen major telecommunication companies, such as UUNet, Sprint, Qwest, XO Network, and AT&T, whose high-speed global networks form the Internet backbone. Tier-1 ISPs do not buy network capacity from other providers; instead, they sell or lease access to their backbone resource to smaller Tier-2 ISPs, such as America Online and Broadwing. Tier-3 ISPs are typically regional service providers such as Verizon and RCN through whom most enterprises connect to the Internet. Figure 1.1 illustrates the architecture of a typical Tier-1 ISP network. Each Tier-1 ISP operates multiple IP/MPLS (multi-protocol label switching), and sometimes ATM (asynchronous transfer mode), backbones with speeds varying anywhere from T3 to OC-192 (optical carrier level 192, ∼10 Gbps). These backbones are interconnected through peering agreements between ISPs to form the Internet backbone. The backbone is designed to transfer large volumes of traffic as quickly as possible between networks. Enterprise networks are often linked to the rest of the Internet via a variety of links, anywhere from a T1 to multiple OC-3 lines, using a variety of Layer 2 protocols, such as Gigabit Ethernet, frame relay, and so on. These enterprise networks are then overhauled into service provider networks through edge routers. An edge router can aggregate links from multiple enterprises. Edge routers are interconnected in a pool, usually at a Point of Presence (POP) Figure 1.1 Network map of a Tier-1 ISP, XO Network
1.1 ARCHITECTURE OF THE INTERNET:PRESENT AND FUTURE 3 Internet ISP backbone Point of presence (POP) Point of presence Core Core (POP) route outer Edge router Switch Switch Edge Edge router router E-commerce server Enterprise Enterprise network network Figure 1.2 Point of presence (POP). of a service provider,as shown in Figure 1.2.Each POP may link to other POPs of the same ISP through optical transmission/switching equipment,may link to POPs of other ISPs to form a peering,or link to one or more backbone routers.Typically,a POP may have a few backbone routers in a densely connected mesh.In most POPs,each edge router connects to at least two backbone routers for redundancy.These backbone routers may also connect to backbone routers at other POPs according to ISP peering agreements.Peering occurs when ISPs exchange traffic bound for each other's network over a direct link without any fees Therefore,peering works best when peers exchange roughly the same amount of traffic Since smaller ISPs do not have high quantities of traffic,they often have to buy transit from a Tier-1 provider to connect to the Internet.A recent study of the topologies of 10 service providers across the world shows that POPs share this generic structure [3]. Unlike POPs,the design of backbone varies from service provider to service provider.For example,Figure 1.3 illustrates backbone design paradigms of three major service providers (a) (b) (c) Figure 1.3 Three distinct backbone design paradigms of Tier-1 ISPs.(a)AT&T:(b)Sprint; (c)Level 3 national network infrastructure [3]
Book1099 — “c01” — 2007/2/16 — 18:26 — page 3 — #3 1.1 ARCHITECTURE OF THE INTERNET: PRESENT AND FUTURE 3 Internet ISP backbone Edge router Edge router Switch Switch Core router Core router Point of presence (POP) Edge router Enterprise network Enterprise network Point of presence (POP) E-commerce server Figure 1.2 Point of presence (POP). of a service provider, as shown in Figure 1.2. Each POP may link to other POPs of the same ISP through optical transmission/switching equipment, may link to POPs of other ISPs to form a peering, or link to one or more backbone routers. Typically, a POP may have a few backbone routers in a densely connected mesh. In most POPs, each edge router connects to at least two backbone routers for redundancy. These backbone routers may also connect to backbone routers at other POPs according to ISP peering agreements. Peering occurs when ISPs exchange traffic bound for each other’s network over a direct link without any fees. Therefore, peering works best when peers exchange roughly the same amount of traffic. Since smaller ISPs do not have high quantities of traffic, they often have to buy transit from a Tier-1 provider to connect to the Internet. A recent study of the topologies of 10 service providers across the world shows that POPs share this generic structure [3]. Unlike POPs, the design of backbone varies from service provider to service provider. For example, Figure 1.3 illustrates backbone design paradigms of three major service providers Figure 1.3 Three distinct backbone design paradigms of Tier-1 ISPs. (a) AT&T; (b) Sprint; (c) Level 3 national network infrastructure [3]
4 INTRODUCTION in the US.AT&T's backbone design includes large POPs at major cities,which in turn fan out into smaller per-city POPs.In contrast,Sprint's backbone has only 20 well connected POPs in major cities and suburban links are back-hauled into the POPs via smaller ISPs. Most major service providers still have the AT&T backbone model and are in various stages of moving to Sprint's design.Sprint's backbone design provides a good solution to service providers grappling with a need to reduce capital expenditure and operational costs associ- ated with maintaining and upgrading network infrastructure.Interestingly,Level 3 presents another design paradigm in which the backbone is highly connected via circuit technology such as,MPLS,ATM or frame relays.As will be seen later,this is the next generation of network design where the line between backbone and network edge begins to blur. Now,let us see how network design impacts on the next generation routers.Router design is often guided by the economic requirements of service providers.Service providers would like to reduce the infrastructure and maintenance costs while,at the same time, increasing available bandwidth and reliability.To this end,network backbone has a set of well-defined,narrow requirements.Routers in the backbone should simply move traffic as fast as possible.Network edge,however,has broad and evolving requirements due simply to the diversity of services and Layer 2 protocols supported at the edge.Today most POPs have multiple edge routers optimized for point solutions.In addition to increasing infrastructure and maintenance costs,this design also increases the complexity of POPs resulting in an unreliable network infrastructure.Therefore,newer edge routers have been designed to support diversity and are easily adaptable to the evolving requirements of service providers. This design trend is shown in Table 1.1,which lists some properties of enterprise,edge,and core routers currently on the market.As we will see in the following sections,future network designs call for the removal of edge routers altogether and their replacement with fewer core routers to increase reliability,throughput,and to reduce costs.This means next generation routers would have to amalgamate the diverse service requirements of edge routers and the strict performance requirements of core routers,seamlessly into one body.Therefore,the real question is not whether we should build highly-flexible,scalable,high-performance routers,but how? 1.1.2 The Future As prices of optical transport and optical switching sharply decrease,some network designers believe that the future network will consist of many mid-size IP routers or MPLS TABLE 1.1 Popular Enterprise,Edge,and Core Routers in the Market Model Capacitya Memory Power Features Cisco 7200 256MB 370W QoS,MPLS,Aggregation Cisco 7600 720Gbps 1GB QoS,MPLS,Shaping Cisco 10000 51.2Gbps 1200W QoS,MPLS Cisco 12000 1.28Tbps 4GB 4706W MPLS,Peering Juniper M-320 320Gbps 2GB 3150W MPLS,QoS,VPN Cisco CRS 92Tbps 4GB 16.560W MPLS,Qos,Peering Juniper TX/T-640 2.5Tbps/640 Gbps 2GB 4550W/6500W MPLS,QoS,Peering Note that the listed capacity is the combination of ingress and egress capacities
Book1099 — “c01” — 2007/2/16 — 18:26 — page 4 — #4 4 INTRODUCTION in the US. AT&T’s backbone design includes large POPs at major cities, which in turn fan out into smaller per-city POPs. In contrast, Sprint’s backbone has only 20 well connected POPs in major cities and suburban links are back-hauled into the POPs via smaller ISPs. Most major service providers still have the AT&T backbone model and are in various stages of moving to Sprint’s design. Sprint’s backbone design provides a good solution to service providers grappling with a need to reduce capital expenditure and operational costs associated with maintaining and upgrading network infrastructure. Interestingly, Level 3 presents another design paradigm in which the backbone is highly connected via circuit technology such as, MPLS, ATM or frame relays. As will be seen later, this is the next generation of network design where the line between backbone and network edge begins to blur. Now, let us see how network design impacts on the next generation routers. Router design is often guided by the economic requirements of service providers. Service providers would like to reduce the infrastructure and maintenance costs while, at the same time, increasing available bandwidth and reliability. To this end, network backbone has a set of well-defined, narrow requirements. Routers in the backbone should simply move traffic as fast as possible. Network edge, however, has broad and evolving requirements due simply to the diversity of services and Layer 2 protocols supported at the edge. Today most POPs have multiple edge routers optimized for point solutions. In addition to increasing infrastructure and maintenance costs, this design also increases the complexity of POPs resulting in an unreliable network infrastructure. Therefore, newer edge routers have been designed to support diversity and are easily adaptable to the evolving requirements of service providers. This design trend is shown in Table 1.1, which lists some properties of enterprise, edge, and core routers currently on the market. As we will see in the following sections, future network designs call for the removal of edge routers altogether and their replacement with fewer core routers to increase reliability, throughput, and to reduce costs. This means next generation routers would have to amalgamate the diverse service requirements of edge routers and the strict performance requirements of core routers, seamlessly into one body. Therefore, the real question is not whether we should build highly-flexible, scalable, high-performance routers, but how? 1.1.2 The Future As prices of optical transport and optical switching sharply decrease, some network designers believe that the future network will consist of many mid-size IP routers or MPLS TABLE 1.1 Popular Enterprise, Edge, and Core Routers in the Market Model Capacitya Memory Power Features Cisco 7200 – 256 MB 370 W QoS, MPLS, Aggregation Cisco 7600 720 Gbps 1 GB – QoS, MPLS, Shaping Cisco 10000 51.2 Gbps – 1200 W QoS, MPLS Cisco 12000 1.28 Tbps 4 GB 4706 W MPLS, Peering Juniper M-320 320 Gbps 2 GB 3150 W MPLS, QoS, VPN Cisco CRS 92 Tbps 4 GB 16,560 W MPLS, Qos, Peering Juniper TX/T-640 2.5 Tbps/640 Gbps 2 GB 4550 W/6500 W MPLS, QoS, Peering aNote that the listed capacity is the combination of ingress and egress capacities
1.2 ROUTER ARCHITECTURES 5 Parallel Large-capacity WAN links uter Mid-size core router -Intra POP interconnection links Hub-to-core inks 多色巴8多彩 形③巴888③ 8888888③ Access/Hub routers Access/Hub routers Figure 1.4 Replacing a cluster of mid-size routers with a large-capacity scalable router. switches at the network edge that are connected to optical crossconnects (OXCs),which are then interconnected by DWDM transmission equipment.The problem for this approach is that connections to the OXC are usually high bit rates,for example,10 Gbps for now and 40 Gbps in the near future.When the edge routers want to communicate with all other routers,they either need to have direct connections to those routers or connect through multiple logical hops (i.e.,routed by other routers).The former case results in low link utilization while the latter results in higher latency.Therefore,some network designers believe it is better to build very large IP routers or MPLS switches at POPs.They aggregate traffic from edge routers onto high-speed links that are then directly connected to other large routers at different POPs through DWDM transmission equipment.This approach achieves higher link utilization and fewer hops(thus lower latency).As a result,the need for an OXC is mainly for provisioning and restoring purposes but not for dynamic switching to achieve higher link utilization. Current router technologies available in the market cannot provide large switching capacities to satisfy current and future bandwidth demands.As a result,a number of mid- size core routers are interconnected with numerous links and use many expensive line cards that are used to carry intra-cluster traffic rather than revenue-generating users'or wide-area-network (WAN)traffic.Figure 1.4 shows how a router cluster is replaced by a large-capacity scalable router,saving the cost of numerous line cards and links,and real estate.It provides a cost-effective solution that can satisfy Internet traffic growth without having to replace routers every two to three years.Furthermore,there are fewer individual routers that need to be configured and managed,resulting in a more efficient and reliable system. 1.2 ROUTER ARCHITECTURES IP routers'functions can be classified into two categories:datapath functions and control plane functions [4]
Book1099 — “c01” — 2007/2/16 — 18:26 — page 5 — #5 1.2 ROUTER ARCHITECTURES 5 Hub-to-core links Mid-size core router Intra POP interconnection links Parallel WAN links Large-capacity core router Access/Hub routers Access/Hub routers Figure 1.4 Replacing a cluster of mid-size routers with a large-capacity scalable router. switches at the network edge that are connected to optical crossconnects (OXCs), which are then interconnected by DWDM transmission equipment. The problem for this approach is that connections to the OXC are usually high bit rates, for example, 10 Gbps for now and 40 Gbps in the near future. When the edge routers want to communicate with all other routers, they either need to have direct connections to those routers or connect through multiple logical hops (i.e., routed by other routers). The former case results in low link utilization while the latter results in higher latency. Therefore, some network designers believe it is better to build very large IP routers or MPLS switches at POPs. They aggregate traffic from edge routers onto high-speed links that are then directly connected to other large routers at different POPs through DWDM transmission equipment. This approach achieves higher link utilization and fewer hops (thus lower latency). As a result, the need for an OXC is mainly for provisioning and restoring purposes but not for dynamic switching to achieve higher link utilization. Current router technologies available in the market cannot provide large switching capacities to satisfy current and future bandwidth demands. As a result, a number of midsize core routers are interconnected with numerous links and use many expensive line cards that are used to carry intra-cluster traffic rather than revenue-generating users’ or wide-area-network (WAN) traffic. Figure 1.4 shows how a router cluster is replaced by a large-capacity scalable router, saving the cost of numerous line cards and links, and real estate. It provides a cost-effective solution that can satisfy Internet traffic growth without having to replace routers every two to three years. Furthermore, there are fewer individual routers that need to be configured and managed, resulting in a more efficient and reliable system. 1.2 ROUTER ARCHITECTURES IP routers’ functions can be classified into two categories: datapath functions and control plane functions [4]
INTRODUCTION The datapath functions such as forwarding decision,forwarding through the backplane, and output link scheduling are performed on every datagram that passes through the router. When a packet arrives at the forwarding engine,its destination IP address is first masked by the subnet mask (logical AND operation)and the resulting address is used to lookup the forwarding table.A so-called longest prefix matching method is used to find the output port.In some applications,packets are classified based on 104 bits that include the IP source/destination addresses,transport layer port numbers (source and destination),and type of protocol,which is generally called 5-tuple.Based on the result of classification, packets may be either discarded(firewall application)or handled at different priority levels. Then,time-to-live(TTL)value is decremented and a new header checksum is recalculated. The control plane functions include the system configuration,management,and exchange of routing table information.These are performed relatively infrequently.The route controller exchanges the topology information with other routers and constructs a routing table based on a routing protocol,for example,RIP(Routing Information Proto- col),OSPF(Open Shortest Path Forwarding),or BGP(Border Gateway Protocol).It can also create a forwarding table for the forwarding engine.Since the control functions are not performed on each arriving individual packet,they do not have a strict speed constraint and are implemented in software in general. Router architectures generally fall into two categories:centralized (Fig.1.5a)and distributed (Fig.1.5b). Figure 1.5a shows a number of network interfaces,forwarding engines,a route controller (RC),and a management controller(MC)interconnected by a switch fabric.Input interfaces send packet headers to the forwarding engines through the switch fabric.The forwarding engines,in turn,determine which output interface the packet should be sent to.This infor- mation is sent back to the corresponding input interface,which forwards the packet to the right output interface.The only task of a forwarding engine is to process packet headers and is shared by all the interfaces.All other tasks such as participating in routing protocols, reserving resource,handling packets that need extra attention,and other administrative and maintenance tasks,are handled by the RC and the MC.The BBN multi-gigabit router [5] is an example of this design. The difference between Figure 1.5a and 1.5b is that the functions of the forwarding engines are integrated into the interface cards themselves.Most high-performance routers use this architecture.The RC maintains a routing table and updates it based on routing pro- tocols used.The routing table is used to generate a forwarding table that is then downloaded Route Route Forwarding controller controllr Interface engine Forwanling enrine Forwarding Interface Imerface engine Switch fabric Interface Switch fabric Forwanding engine Forwarding Interface engine Management Management ni吧en (a) (b) Figure 1.5 (a)Centralized versus (b)distributed models for a router
Book1099 — “c01” — 2007/2/16 — 18:26 — page 6 — #6 6 INTRODUCTION The datapath functions such as forwarding decision, forwarding through the backplane, and output link scheduling are performed on every datagram that passes through the router. When a packet arrives at the forwarding engine, its destination IP address is first masked by the subnet mask (logical AND operation) and the resulting address is used to lookup the forwarding table. A so-called longest prefix matching method is used to find the output port. In some applications, packets are classified based on 104 bits that include the IP source/destination addresses, transport layer port numbers (source and destination), and type of protocol, which is generally called 5-tuple. Based on the result of classification, packets may be either discarded (firewall application) or handled at different priority levels. Then, time-to-live (TTL) value is decremented and a new header checksum is recalculated. The control plane functions include the system configuration, management, and exchange of routing table information. These are performed relatively infrequently. The route controller exchanges the topology information with other routers and constructs a routing table based on a routing protocol, for example, RIP (Routing Information Protocol), OSPF (Open Shortest Path Forwarding), or BGP (Border Gateway Protocol). It can also create a forwarding table for the forwarding engine. Since the control functions are not performed on each arriving individual packet, they do not have a strict speed constraint and are implemented in software in general. Router architectures generally fall into two categories: centralized (Fig. 1.5a) and distributed (Fig. 1.5b). Figure 1.5a shows a number of network interfaces, forwarding engines, a route controller (RC), and a management controller (MC) interconnected by a switch fabric. Input interfaces send packet headers to the forwarding engines through the switch fabric. The forwarding engines, in turn, determine which output interface the packet should be sent to. This information is sent back to the corresponding input interface, which forwards the packet to the right output interface. The only task of a forwarding engine is to process packet headers and is shared by all the interfaces. All other tasks such as participating in routing protocols, reserving resource, handling packets that need extra attention, and other administrative and maintenance tasks, are handled by the RC and the MC. The BBN multi-gigabit router [5] is an example of this design. The difference between Figure 1.5a and 1.5b is that the functions of the forwarding engines are integrated into the interface cards themselves. Most high-performance routers use this architecture. The RC maintains a routing table and updates it based on routing protocols used. The routing table is used to generate a forwarding table that is then downloaded Management controller Interface Interface Interface Forwarding engine Forwarding engine Route controller Forwarding engine Switch fabric Management controller Route controller Switch fabric Interface Forwarding engine Interface Forwarding engine Interface Forwarding engine (a) (b) Interface Forwarding engine Interface Forwarding engine Interface Forwarding engine Figure 1.5 (a) Centralized versus (b) distributed models for a router