Hierarchically Switched Networks

This work was funded by the National High Technology Research and Development Program of China (“863” Program) under Grant No. 2007AA01Z214.

1 Challenges Facing the Internet
The Internet is one of the most influential inventions of the twentieth century. It provides people with new means of communicating, exchanging, and acquiring information. Indeed, it has dramatically accelerated the progress towards more connected information societies. More than 3 billion people worldwide use the Internet, and it should not escape mention that in populous countries such as China and India, over three quarters of the population are still unable to surf online. The reason why the Internet has developed so rapidly is that it sates the demands for an information society, and adopts concise packet switching protocols and flexible routing methods.

    Unlike traditional circuit switching, packet switching requires complete routing technology. It takes advantage of computer intelligence to periodically exchange information among routers and then form a routing table. Based on the destination address (written on the surface of the data packet) and the saved routing table, each router transfers a data packet to the next hop until the packet reaches its destination. Forwarding operations and updating of the table are performed automatically by the routers without any manual intervention. Because routers automatically adapt to the network structure, people can construct networks as they like, and network architecture can have random connections.  Where the reliability of network components, especially communication lines, is very low, a network structure with random connections and automatic routing capability is very effective. Indeed, routing technology is the very core of the Internet.

    In the early stages of development, the Internet excelled other network architectures with its simple network protocol, packet switching technology, and routing technology. However, as technologies developed and advanced applications were introduced, and as the size of the Internet grew far beyond what its designers originally imagined, the advantages of the Internet were gradually undermined. Some of the features that made the early Internet so effective are now not advantageous at all, and some have even become obstacles in the Internet’s development.

    As the network scale has enlarged and demand for real-time communication increased, the Internet has encountered a series of problems. These include:

    (1) Huge-sized routing tables due to the large-scale network. This prevents quick and effective forwarding of data packets.

    (2) Local network behaviors (such as partial change of network topology, failure and recovery of links or devices, and configuration or operation mistakes of network administrators) are being treated as global behaviors and are being broadcasted worldwide. This requires all routing information to be changed. As a result, the burden on backbone network routers becomes unbearable, and after a network event, the convergence time of routing information exceeds one minute. This causes a large number of data packets to circulate in the network.

    (3) Routers are becoming increasingly complex, and their costs and power-consumption have increased accordingly.

    (4) Network protocols are becoming more complicated due to the addition of virtual circuit switching technology. Virtual circuit switching technology draws on the strengths of circuit switching technology in order to overcome some of the shortcomings of packet switching technology.

    (5) The advantages of randomly-connected network architecture are being offset against the high reliability of optical communication lines.

    (6) Full and reasonable use of network channel resources is difficult to achieve. Network designers cannot assign a suitable bandwidth for each channel because the exact route of a data packet cannot be determined manually, and the data packet is likely to be detoured via other channels.

    (7) Carrier-class Quality of Service (QoS) is difficult to achieve due to a slow end-to-end recovery approach, and lack of self-healing capabilities.

    (8) Effective management and control is difficult to implement due to the uncertainty of network behaviors.

    (9) Backbone network devices are vulnerable to fatal security threats. The network address space is not strictly distinguished from the user address space, and backbone signaling is completely integrated with user network signaling.

    (10) Malicious network behaviors cannot be effectively detected and controlled because the network source address can be easily forged.

    All these problems are fatal. Moreover, because early designers underestimated the scale of the Internet, the IPv4 address space will be used up in one to two years. Many private addresses are currently being used, but this weakens end-to-end communication capability. If IPv6 protocol is adopted, and the number of address spaces dramatically expanded without consideration of the network hierarchy, routing tables will also be dramatically increased. Routers will become more complex, and more serious bottlenecks will appear in the network. To date, there have been many improvement measures, but these cannot solve the problems completely while they increase the complexity of network protocols. Therefore, there is a pressing need for significant reform of the Internet.

    To deal with the Internet’s tough challenges, this paper proposes a new network architecture: an hierarchically switched network. This architecture is designed to:

• Completely exclude routers from the network;
• Reintroduce the principle of simplicity into the network;
• Make the data packet path predictable in order to reasonably utilize the network’s channel resources;
• Localize events such as topology change, failure and recovery of devices or communication lines, and mis operations of network administrators;
• Make the quick self-healing capability of a network independent of other complicated networks, such as Synchronous Digital Hierarchy(SDH)/Synchronous Optical Network (SONET);
• Enable the natural formation of a multicast tree;
• Separate the backbone address space from user address space;
• Allow malicious behaviors to be easily traced.

    No matter which reform or new technology is applied to the Internet, it should be fully compatible with existing Internet protocols; otherwise, it will be unfeasible.

2 Basic Structure of Hierarchically Switched Networks
In the early design of the Internet, reliability was a core principle. At the time, this principle was warranted because both channel failure rate and bit error rate were very high, and designers also hoped the Internet would survive wars and natural disasters. But few could have predicted how this network would apply to real-time multimedia services such as voice and video. Even the number of network users today would have been beyond their imagination; had they been able to predict this, they would have planned more carefully for address space. Taking reliability as a core principle, early designers adopted a dispersed, distributed, and non-centric approach to their designs. Ethernet is a typical example of such architecture. It consists of many computers that are interconnected with thick or thin cables. All computers are peers without any controller or coordinator, and the failure of one computer does not adversely impact another. The topology of the Internet is a mesh with random connections. There is no center or hierarchy in the Internet. Each node can randomly connect to other nodes. As long as each switching device has two or more channels, the network is regarded as highly reliable. The assignment of IP addresses is based on the network identity as well as the host number in the network. And the network identity, which plays a decisive role in the routing algorithm, is flat rather than hierarchical. When the number of such flat IP addresses becomes exceedingly large, it is impossible to develop an efficient switching algorithm for routing information. Nor is it possible to develop a quick routing table lookup algorithm. This is the exact sticking point of Internet routing. The randomly-connected structure and flat address space does not conform to the current thinking of human beings, and does not meet the efficient processing requirement of computers. Moreover, they are of poor scalability and can only be applied in very small systems. In fact, all organizations and address spaces of human society are hierarchical: a nation, a school, an enterprise, an army, postal address space, subject categories and cataloguing of books. A traditional telephone system is a manageable, controllable, scalable system that guarantees communication quality, and is also hierarchical. The domain name system of the Internet was originally flat, but it had to adopt hierarchical structure because it became infeasible once more than several hundred computers were connected. As for the Ethernet architecture, buses have become extinct from use. People now use hubs or switches. When ports are not sufficient, or the distance is extensive, several switches are cascaded to form a typical star or tree structure. In short, the hierarchical structure is present everywhere. From a management perspective, the hierarchical structure itself represents a kind of dispersal or distribution.  Upper level management cannot and does not concern itself excessively about things that should be done at a lower level; an upper level manager may not be aware of changes made by a lower level manager within their jurisdiction. This enables the network system to be fully scalable. Reference [1] proposed the first hierarchical structure. However, this hierarchical structure has been largely ignored because its addressing method, still affected by the routing approach, is not flexible enough.  Researchers have come to realize that when the scale of a network becomes exceedingly large, the scalability of its routing system is the first thing to be challenged. Hence, attention has been focused on hierarchy, and methods such as landmark hierarchy[2], geographical hierarchy, and Internet Service Provider (ISP)-rooted hierarchy[3], have been proposed.

    The hierarchically switched network proposed in this paper simply and clearly divides the network into two parts: backbone and user networks (as shown in Figure 1).

    In Figure 1, all communication entities come from user networks. That is to say, communication is required only within a user network, or between hosts of two user networks (e.g. PCs, servers, or any wireless or wired terminals that can access the network for communication). No user can request to communicate with devices in the backbone. The function of the backbone is very simple: it forwards data packets from one user network to another. Therefore, the backbone can be considered as a large IP switch. In a large-scale system, however, it is impossible to make such a switch that can connect all user networks in the world. This virtual large switch can be physically implemented with a simple tree structure. Figure 2 illustrates a two-layer tree; but in reality, the tree can be many layers, just like in a telephone network.

    The fatal flaw of the tree structure is that failure of any node or channel will cause all subtrees under the node to disconnect. This defect can be overcome with logic nodes and logic channels, as shown in Figure 3.

    Figure 3 illustrates a basic tree. Regardless of its level, a node may have many lower level nodes under it. In Figure 3, the blue boxes represent IP switches. Two or more switches make a logic node. The switches in a logic node are interconnected with high speed channels, and with the control software of the logic node, they are known as a single node to other nodes. Between the two levels of logic nodes there is a set of physical channels that are used to connect the IP switches of the nodes. This forms a logic channel (circled with broken lines in Figure 3) through the control software of logic nodes. Such a structure is tree-like in design, but physically, it has complicated connections that solve the problem of single point failure.

3 Expansion of the Tree Structure
Despite its advantages, the tree structure is less flexible than the mesh structure (which allows random connections) of the existing Internet. For example, when transmitting a data packet between two user networks on the leaves of a tree, the packet must go upward from the source user network to the root of the subtree of the two user networks. It then goes downward to the destination user network. In reality,  the two user networks may be very close to each other. Supposing two ISPs deliver access services in City A at the same time, there will be two trees extending to the city, but the meeting point of the two trees might be in City B. When two communicating user networks, both in City A and close to each other, are connected to different ISP trees, data packets must first go along the ISP’s tree to the meeting point in City B, then go down the tree of the other ISP to the target user network of the other ISP in City A. If there are interconnection channels between the two ISP trees in City A, the detour to City B can be avoided. Figure 4 illustrates a network structure that meets such requirements.

    If we treat equally the channels represented by broken lines and solid lines in Figure 4, and allow more channels in broken lines to be added, the network topology is almost the same as that of the existing Internet. The detour to upper-level nodes can be reduced or even eliminated and flexibility is enhanced. But such a network structure comes at the cost of the advantages of the tree structure. To ensure both the flexibility of the Internet and the advantages of tree structure, the channels in solid lines and broken lines in Figure 4 should be distinguished as tree channels and shortcut channels (or through channels) respectively. A shortcut channel can be a single physical channel or a logic channel made up of several physical channels. The shortcut channel functions no differently from the tree channel, but in switching user data packets, the shortcut channel is treated as a special case and given high priority.

    When connecting via shortcut channels, data packets can be forwarded not only to the opposite end of the shortcut channel, but also to a farther node. For example, in Figure 4, logic node E’ can not only forward the data packet to J via the E’-J shortcut channel, but also to remote logic nodes L and M via the E’-J shortcut channel. This forwarding involves direct and indirect shortcut channel technologies. Details about these technologies can be found in Reference [4] and it is not intended to discuss them here.

4 Switching Method
After the backbone network in a tree structure is constructed and configured with a certain number of shortcut channels, any routing protocol can be cancelled, and simple switching of IP data packets can be achieved. Take for example the IPv6 address format. The low 64 bits are used as the interface identifier and cannot be used by the backbone devices, while the high 64 bits are routable addresses used by the backbone devices for forwarding IP packets.
In the IPv6 address structure, the Site Local (SL) part is assigned to users. Because the network topology is a tree, an ISP can divide the addresses it receives into several variable-length fields, which are called Switching Fields (denoted as SFi ). Each switching field corresponds to a layer of the tree; a high-ranking switching field corresponds to a high layer of the tree.

    User networks are at the edges of the backbone network. A data packet sent from a user network always enters the backbone tree via a leaf node. Supposing this logic leaf node corresponds to switching field SFi , the packet switching process is very simple if no shortcut channel is involved:

    (1) The prefix of the IP packet’s destination address is compared with the address prefix of the logic node.

    (2) If the two prefixes are not equal, the packet goes upward. In this event, it selects an uplink channel and forwards the packet to an upper-level logic node.

    (3) If the two prefixes are equal, the packet goes downward. In this event, it selects a downlink logic channel according to the value of SFi  (e.g. if the value of SFi  is 5, the logical channel 5 should be chosen), and forwards the packet to a lower-level logic node.
When shortcut channels are involved, packet switching is a little complex. Before the above steps, it must first be determined whether the logic node has any shortcut channel. If there are shortcut channels, each channel will be assigned a shortcut channel table, which contains address prefixes of the direct shortcut logic node of the channel (i.e. the opposite logic node of the shortcut channel). This table also contains remote, indirect shortcut logic nodes of the channel. If the address prefix of the packet is the same as that of any logic node in the table, the packet will be forwarded via the shortcut channel; otherwise, the above steps will be executed to complete packet switching.

    In sum, once the address structure is associated with the network topology, packet switching becomes quite simple. It can be done by simply comparing the prefix of the packet’s destination address with the value of a related switching field, and routing information that is exchanged globally becomes unnecessary.

5 Benefits of an Hierarchically Switched Network
Associating the tree structure with address structure brings a series of benefits to the network.

    First, the tree structure is a deterministic structure. Packet flow within the network is predictable, as is network behavior. As a result, the network becomes more controllable and manageable. The ISP can simply divide network management into two layers: logic node and entire network. Logic node management involves monitoring states, flows, performances, and charging information from switches and internal channels in each logic node, as well as from external channels of each logic node (i.e. channels between local logic node and other logic nodes). Management of the entire network is simpler because management information of all logic nodes is integrated to give a overall picture of the network. This information includes network status, external channel load, and charging database, and can be displayed in appropriate diagrammatic forms. In addition, a network with a tree structure is scalable. Horizontally, logic nodes can be increased easily; while vertically, layers can be added to the tree to enable more users to access the network.

    Second,  because communication paths are certain, management, assignment, and admission control of path resources can be achieved.  Accordingly, QoS guarantee is also possible. For QoS to be guaranteed, resource management, admission control, and output scheduling is necessary. Resource management involves registration and allocation of communication path resources, such as channel capacity and port buffer, ensuring existing communication flows get enough resources. Admission control involves accepting or rejecting new communication requests based on remaining resource information. This information is provided by resources management in order to avoid heavy traffic contending for limited resources. Output scheduling is designed to manage the output queue according to the priorities of communication flows. The existing Internet cannot guarantee QoS. It cannot even determine the path for a data packet. How then can we expect it to reserve resources for the path and implement admission control?
Third, certainty about the communication path enables the communication load to be estimated and channel capacity to be configured well. This avoids low resource use that arises from an unbalanced network load, and which is quite common in existing networks. It also reduces the load from complicated and inefficient Traffic Engineering (TE).

    Fourth, by associating network topology with address structure, the tree adopts IP switching instead of IP routing. In this way, it is released from routing-related work such as routing information exchange in the entire network, maintenance, management and update of the routing table, and looking up unwieldy routing or forwarding tables for IP packets. In this structure, IP packet forwarding is quick and simple, and network performance is enhanced.
Fifth, the tree structure localizes network events. For example, the failure and recovery of any node or channel does not have an impact on remote packet switching algorithms. Also, configuration and management of logic nodes is much simpler than that of a routing system. Network operation and maintenance personnel are unlikely to make mistakes during operations. Even if there is an operational error, it does not have any negative impact on the worldwide network, unlike the routing system. As there are no Border Gateway Protocols (BGPs), all core routers are free from the heavy burdens of updates and withdrawals of BGPs.

    Sixth, the security of the network itself is greatly enhanced. In existing networks, the port IP address of the core router resides in the same address space as the users’ host IP addresses. So any user can carry out a Distributed Denial-of-Service (DDOS) attack on any core router. In hierarchically switched networks, the address space of the backbone network and user networks can be easily separated, so user data packets can transverse the backbone network without interfering with its devices. In addition, in the existing Internet, a user can fake their source address to avoid the network tracing their malicious behavior. In an hierarchically switched network architecture, the address prefix of a user network is the same as that of a device port at the edge of the backbone network, so any false use of a source address can be immediately detected and reported.

    Seventh, logic channel technology brings two benefits: the channel’s capacity for self-healing, and additional means of expanding channel capacity. The self-healing capability ensures that if a physical channel fails, the overall capacity of the logical channel is only slightly reduced, but communication of other channels can still proceed. This is a necessary condition for guaranteeing QoS. As for enlarging channel capacity, the logic channel capacity can be expanded by increasing the bandwidth of each physical channel or the number of physical channels.

    Eighth, network devices can be greatly improved in terms of complexity, reliability, cost, and power consumption.

6 Deployment of Hierarchically Switched Networks
The key to success in the reformative reconstruction of existing systems lies in the deployment of new systems. The new systems should be compatible and easily inter-connectable with existing systems. Due to incompatibility between IPv4 and IPv6, the deployment of IPv6 has been very slow. The hierarchically switched network, on the other hand, does not have any incompatibility problem caused by the coexistence with existing networks, does not require any modification of those existing networks, and does not involve the application layer. The hierarchically switched network can be deployed in a gradual manner.

    With the development of Gigabit Ethernet (GE)—10GE, 100GE, and long-distance high-speed transmission technologies (e.g. 10 Gbit/s, 40 Gbit/s, and even 100 Gbit/s)—the current Internet can easily apply the rates of long-distance backbone network in user access networks. These rates are obviously insufficient for the backbone network, and due to the bottleneck problem caused by routers, the Terabit per second transmission capability of optical fiber cannot be fully exploited. But for user access networks, which serve limited user groups, the demand for voice, video, and data communications can be satisfied even with existing routing technology. Therefore, the issue of solving fatal defects in the Internet is not so pressing in user networks as it is in the backbone network.

    In addition to non-real time applications, the backbone network has to process millions of flows of video and voice traffics. The existing routing structure, which is characterized by low efficiency, low rate, slow self-healing, difficult to realize multicast, and lack of effective QoS guarantee, has become a critical obstacle for tri-network convergence (i.e. convergence of telecom networks, radio and television networks, and the Internet). Solving the problems of the backbone network is the most urgent issue for the existing Internet. The Internet industry has devised numerous QoS schemes and methods which all focus on the backbone network. Unfortunately, these methods are extremely complicated, ineffective, and hard to deploy. Even their standards are difficult to make.

    In the evolution to the hierarchically switched backbone network, it is proper to do with the ISP’s backbone network or part of the backbone network each time. The address structure of the hierarchical network should have enough space to be easily layered. The IPv6 address structure meets such a requirement and can be directly used in a hierarchically switched network.

    The study of topologies of current ISP backbone networks shows that a hierarchical tree structure is adopted in all layers of these networks except the core nodes (often about a dozen) in the topmost layer. These are randomly and fully interconnected into rings or other forms. If these core nodes are organized into one (or a few) logical node(s), the entire network architecture naturally forms a tree. The tree structure is quite common because it is naturally formed based on the geographical location of nodes. However, the adoption of the routing system has changed everything; the advantages of the tree structure are lost, and orderly network architecture is changed into a disorderly system. In nature, there can be found many large chaos systems, but among artificial systems, only the Internet has such an attribute. Therefore, in reforming the existing backbone network into a hierarchically switched network, existing nodes and channels can be divided into logic nodes and logic channels, and control software for each logical node can be installed without changing the existing network topology.

    The hierarchical structure can also be applied in user access networks. With such a structure, user networks can have hierarchically switched logic nodes and Ethernet switches only, or have Ethernet switches only, so that the technologies involved in network management will be considerably simplified.

7 Conclusions
The new hierarchically switched network architecture overcomes almost all defects of the existing Internet and proves Rekhter’s Law[5] correct. Prototype system and sampling switches with hierarchically switched network architecture as discussed in this paper have been developed and tested on a test platform. Moreover, these systems have long been used in office networks, offering access to IPv6 and IPv4 networks. Experimental results demonstrate that this architecture is feasible, simple to implement, and performs satisfactorily.

References
[1] KLEINROCK L, KAMOUN F. Hierarchical Routing for Large Networks: Performance Evaluation and Optimization [J]. Computer Networks, 1977, 1(3): 155-174.
[2] TSUCHIYA F. The Landmark Hierarchy: A New Hierarchy for Routing in Very Large Networks [C]//Proceedings of Symposium on Communication Architectures and Protocols (SIGCOMM’88), Aug 16-18, 1988, Stanford, CA, USA. New York, NY, USA: ACM, 1988: 35-42.
[3] FRANCIS P. Comparison of Geographical and Provider—Rooted Internet Addressing [J]. Computer Networks and ISDN Systems, 1994, 27(3): 437-448.
[4] 钱华林, 葛敬国, 李俊. 层次交换网络体系结构[M]. 北京: 清华大学出版社, 2008.

[Abstract] The Internet of today is facing serious challenges including lack of routing system scalability, unpredictable network behavior, uncertainty of data packet paths, poor control and manageability, unachieved Quality of Service (QoS), vulnerability of network facilities to Distributed Denial-of-Service (DDOS) attacks, core router complexity, costliness, and high power consumption. All of these defects have their root causes in the routing system. This paper first proposes a new network architecture which combines network typology with addressing. It then highlights that reliability of the tree structure is guaranteed by the concepts of logical node and logical link. Furthermore, shortcut link technology makes tree topology more flexible, and IP routing can be replaced with IP switching. As a result, all flaws in the current Internet architecture can be overcome.