Communications Networks (48740)
University of Technology, Sydney
Statement of Originality
The work contained in this assignment, other than that specifically attributed to another source, is that of the authors. It is recognised that, should this declaration be found to be false, disciplinary action could be taken and the assignments of all students involved will be given zero marks.
This document was written by a student of Communications Networks.
1. Packet Switching An introduction
2.1 The Growing Need for Communication
2.3 Internet (WANs and LANs)
3. Hardware Concepts and Components
3.1 Packet Switching The Layers
3.2 Switches and Routers
3.3 Routing Strategies
3.4 Routing Methods
4. Commonly Used Protocols
5. Application of Packet Switching in the World Today
5.1 Advantages over Circuit Switching
5.2 Companies Producing Packet Switching Technology
5.3 Future Applications
6.1 Summary Points
6.2 Review Questions
7. Bibliography and References
1. Packet Switching An introduction
All communication networks today are comprised of many nodes. Each node needs to be able to communicate with other nodes. Each node may be connected with one or more links, of various speed and reliability. Within a circuit-switched system, if two nodes want to communicate, they will cooperate with other nodes on the network to set up a dedicated link through which to communicate. A packet switched network does not require this rigid link. Communication between nodes is established and maintained by an intermittent flow of small portions of data through one or many different paths. The path taken by each portion of data or packet may depend on the status of links, or algorithms used by switching equipment. Switching is carried out by special nodes on the network which govern the flow of data. Such devices include switches, routers and bridges [GRINSEC p xiii, Derfler & Freed p163, Abeck Hegering & Neumair p 50-56].
Animation 1 Packet Switching
There are many different strategies, algorithms and protocols used to maximise the throughput of packet switching networks. Plus there are two main types of packet switched networks/protocols. One type of switching uses datagrams, which means that each packet is treated individually, sent end-to-end by use of any route that may be active. The second switching method is called a virtual circuit. This type of traffic behaves a lot like circuit switched networks, where communication between to devices will be carried out through a dedicated route. Unlike circuit switching, a virtual circuit permits other traffic to use the same route (or part thereof) concurrently [GRINSEC p 531, Stallings p 304].
In a seminar, held at the Franklin Institutes 2001, Paul Baran claims that the
" new argument seems to be that it is unimportant whether the communications stream is chopped into packets or not " [Baran p 7]
which is an interesting example of how far packet switching has evolved from its early beginnings, to what is has become today.
Packet switching has a very hazy beginning. There is much speculation as to who actually invented it first; however there have been some definite milestones during its short history. In an article on IPIER.COM, packet switching is accredited to a " government laboratory in England " [Internet 101] but fails to mention any names or any further details. In fact, many laboratory experiments with packet switching were being carried out all around the world, most being quite independent of each other. The research that stands out for its impact on packet switching is the research carried out by Paul Baran.
2.1 The Growing Need for Communication
In 1959 Paul Baran joined an organisation called RAND. RAND was set up by the U.S Air force to " preserve the operations research capability created by the Air Force in World War II, and to work on issues of national security." [Baran p 1]. RAND encouraged a freedom with projects and encouraged approaching problems in a unique manner.
At that time, communication between strategic forces command centres was through either short wave wireless links, or through the national telephone company (via circuit switched networks). This provided a gaping hole in the security of their communications system. In the event of a high-altitude nuclear detonation, the short-wave communications would be disrupted for hours. A strategic attack on communications links would render long distance telephone links inactive, providing what Baran describes as an "Achilles heel" [Baran p 1] in RANDs communication system. As the Cold War was developing, a robust communications system was in demand, so Baran decided to start his research into finding new solutions.
Figure 1 Network topologies [Barna Pg 2].
The first thing that Baran noticed was that the main problem with the system was its topology. Currently, RANDs communication network was comprised of centralised and decentralised topologies. In figure 1, diagram a) is an example of a centralised topology, where each node is connected to one central node. This network is extremely vulnerable. Diagram b) is an example of a decentralised topology, where the network appears to branch. This type of network is generally comprised of many centralised networks, hence adding slightly more robustness, as there is now more than one central point in the network. Diagram c) is an example of a distributed topology. Each peer in the network is connected to neighbouring peers through one or more links. This creates a large number of redundancies in the system; however these redundancies offer a considerably higher level of robustness than figures a) or b) could provide.
Baran decided to conduct simulations of networks with varying numbers of redundancies. Level 1 was characterised by a minimum number of connections between nodes. Level 2 had vertical and horizontal connections, offering many more links between nodes. When the order of links was then increased to level 3, Baran made the observation that the system became extremely robust. From this observation, he concluded that it would be " theoretically possible to build extremely reliable communication networks out of unreliable links, by the proper use of redundancy." [Baran p 2] Thus the main idea behind packet switching was born. If a communications link between nodes was attacked, then the node could theoretically still operate within the network due to its redundancy. How was the next obstacle.
Many problems were experienced when developing this distributed network, the first being bit-rates. Synchronisation was not going to be achievable, since the network would have to route data in a manner that could not be established in advance. This would add overhead to the already copious amount of data that was expected to be communicated. Baran overcame this problem by proposing that each routing node in the system contain a buffer that would store the data and re-communicate it at its own pace, the beginnings of store-and-forward packet switching. Data would need to be broken into packets, or as Baran termed them at the time message blocks. This was because the amount of buffering available in computers during the 1970s was low, due to the cost and capabilities of the technology.
Baran started looking at routing strategies, basing his research on adaptive systems, which used previous knowledge to route data. The system would have a limited amount of resources, so it was designed to discard old/less relevant information as well as collecting new information. Each packet would contain a hand-over counter that would increment each time a packet was passed between nodes. This counter would then be examined by the end-system and hence be used to estimate efficiencies/routes through the network. Baran described routing as a hot potato, "You want to get rid of the hot potato as quickly as you can. If your first choice recipient is busy, toss it to your second choice recipient, and so on. If you have no better choice you are allowed to throw the hot potato back to the previous thrower." [Baran, p 4]. Although it sounds primitive, this method of routing is a basis for many routing algorithms today (often called deflection routing). It makes an emphasis on speed, as each node will not need to stop and think. This was envisaged as a good algorithm to route delay-sensitive packets, such as voice.
Some other features Baran incorporated in his design of the packets were sequence numbers and error checking. Sequence numbers were used (and still are today) to inform the receiving node about the order the packets should be re-assembled in. To check for errors in transmission, Baran used CRC (cyclical redundancy check) which is also one of the most common error-checking methods today. I would just like to point out that Baran did not invent the CRC. CRC was a commonly used error-checking algorithm used by many people at the time.
Due to the nature of the system, security was to be very important. Baran devised two levels of cryptography. The first level of security would be on a node-to-node level, where each node knows the key to each of its neighbouring nodes ciphering algorithms. The second level of security would be based on an end-to-end cryptography scheme. Each pair or end users on the network system would somehow agree upon a key to use. One new feature that Baran designed was that each packet would contain the key to the next packet. This was a great idea not only for security, but also for error checking. If a packet is corrupted during transfer, the key may be wrong and hence the next packet that is deciphered will be garbled. The system could very easily detect these errors and request re-transmission (or simply not send an acknowledgment). With a packet switched network, each of these packets would be encouraged to travel across different routes, so that an eavesdropper would have little chance of obtaining all of the keys. Baran admits that such a system has not been built (for the advantages in error detection) but maintains that is a good idea [Baran p 4].
One problem with circuit switched applications is that "silence is the usual message" [Baran p 5]. This is certainly true for phone conversations, which is an inefficient utilisation of communication infrastructure. If there is no information to be exchanged, then a packet switched system will not send or receive information, freeing up the communication resources for other applications. Baran discusses this in his seminar, although another man, W. David Sincoskie, had the same ideas. In 1980, Sincoskie was employed by Bell Labs, and he made the following calculation: " an Ethernet would carry up to 150 simultaneous voice calls, if the calls were coded at 64 kb/s and silent periods removed. This was enough to construct a 1000-line private branch exchange..."[Sincoskie, p 2]. This was an amazing idea, which was later demonstrated in the worlds first prototype broadband central office ERP (Experimental Research Prototype).
For more information on ERP and the future of packet switching, section 6.4 deals with the future applications of packet switching.
The ARPANET is worth mentioning at this point, as it is the basic grass roots of the internet. The Advanced Research Projects Agency (ARPA) Computer Network (NET) has been an important relic for the study of packet communication, because it provides a strong understanding and hence efficient implementation of the packet switching technologies for the internet [Metcalfe, p 23]. In 1969 the ARPANET consisted of four computers, distributed across a large geographical area [Internet 101] and soon grew to over 30 sites in 1996 [Metcalfe p 28]. The ARPANET was based on a store-and-forward packet switched network consisting of end nodes (terminals) and interface message processors (IMPs) which carried out the routing. The topology of the ARPANET was a little ad hoc, but it resembled a distributed network. The ARPANET also allowed study of network behaviour, which would be important to consider when designing packet switching networks. One thing that surprised Metcalfe was the amount of incestuous network traffic [Metcalfe p xxiv-xxv] which is his term for intranet traffic. This traffic was being sent to the IMP and then being routed back into the internal network. This phenomenon prompted new devices to be created to handle internal network traffic. The switching equivalent of the internal IMP (or router) is the switch.
2.3 Internet (WANs and LANs)
In recent years, the growth of the internet has been phenomenal. The technologies that have sprouted from military research and development have bloomed into a worldwide network of communication, providing remote information and control. Many local area networks (LANs) found in the office or even at home have become a part of this growing network of nodes. Packet switching may not be utilised on these LANs (most commonly ethernet), so a bridge may inter-connect the switched networks and the LAN. For example, if a small amount of data is needed to be communicated by a LAN to the internet, it is common to have a dedicated computer which acts as a bridge/router for internet (or inter-subnet) traffic. Recent advances in switching technology have resulted in hardware routers becoming layer 3 switches [Abeck Hegering & Neumair p 415].
3. Hardware Concepts and Components
As described earlier, packet switching relies on two devices switches and routers. Bridges were mentioned as well; however the bridge forms a common path information can travel on between different protocols and topologies. Bridges may carry out some crude switching functions, but will not be discussed in detail. There is an increase in the capability of these devices and others, on the market today. It is not uncommon to find smart devices, with hybrid technologies, performing bridging, switching and routing functions (and more).
3.1 Packet Switching The Layers
To understand how packet switching works, it is important that we first understand what a packet is and how it is formed. To do this, we will study animation 2. In 1977, ISO decided to make a standard for describing packets and how they are formed. This standard is called the open systems interconnection (OSI) reference model [Stallings p 44]. This model describes seven layers, which describe aspects of the network communication vital for getting data from one node to another.
Animation 2 - Encapsulation
Firstly, the end-users computer buffers a piece of data that it wishes to send. This piece of data can be theoretically any length, but for simplicity we will assume it is a short piece of data. If the data is too big, the data will be cut into smaller pieces, which is called segmentation. It is also possible that data may be segmented at intermediate nodes along its journey from the host to the end user if the data is deemed to be too big. Each segment will be appended with some information to identify what it is, where its going and any other relevant information. This information is called a header. Once this is completed, the segments are passed down to the next layer, which performs similar tasks on the segments (which have now become the data). This processes is iterated until the data reaches the final stage, where it is placed on the communication link and sent to the receiving node. The receiving node simply removes the headers from the data and puts all of the segments back together. The process of data being segmented and having a header attached is know as encapsulation.
Table 1 explains each of the seven layers in the OSI model. The top layer (layer 7) is the layer at user level. As the layers go down, they get increasingly primitive, until they reach layer 1, which is the most primitive from an information point of view (ie. It is actually concerned with the physical communication links)
|7||Application Layer||Gives application software access to the OSI environment. This layer contains management functions.|
|6||Presentation Layer||Establishes common ground for applications to communicate with the other layers. This layer formats data and provides syntaxes for applications.|
|5||Session Layer||Provides a service that controls the communication between applications running on end nodes.|
|4||Transportation Layer||Provides a means of communicating between end nodes. Its functions may include sequencing, error detection and optimisation of communication.|
|3||Network Layer||Deals with communication of data on a network. Here, network information is gathered, including addresses, routing information, etc.|
|2||Data Link Layer||Deals with maintaining and optimising the actual connection to the network. It also performs error checking on the communicated data.|
Deals with the physical connection between nodes in a network. It tends to deal with a bit stream rather than any single pieces on information.
Table 1 The seven OSI models [Robinson p 6-7 and Stallings p 51-54]
The application of this model will be discussed in section 5, with regard to commonly used protocols.
The use of these layers was introduced to break down the complexity of communications. Each layer could be seen as an object in an object-oriented design approach. This makes designing a complex protocol a lot easier; plus if certain layers do not function correctly, it should be a simple task to isolate a layer and work on it, if this design approach is taken.
3.2 Switches and Routers
Switches and routers are used in packet switching networks to guide packets towards their destination. A switch is a device with a certain number of physical ports, through which either nodes (such as computers, printers or routers) or other switches can be connected. A switch consists of a few key elements. Firstly, the switch has a small amount of processing capability, so that it can work out what device is connected to what port. To help the switch perform this function quickly, a table of network addresses is kept within the switch, with a capacity of around 4000 or more addresses. Depending on the nature of the switch, these tables can be statically or dynamically updated. The key component of the switch is the switching fabric, which is the point where data is transferred from one port of the switch to another. Switches need only know the destination of packets, so generally they will be classed as layer 2 devices, which means that they communicate and understand only layers 1 and 2 of the OSI model. Since layer 2 devices only deal with the bottom two layers, they handle packets according to MAC addresses. Newer, hybrid switches (layer 3 switches) are becoming more complex and can communicate as a layer 3 device.
The main problem faced by switches is contention. Contention is when two packets are sent to one destination in one instance of time. This would obviously cause some problems. Switches can deal with contention in different ways. One method is to buffer one of the packets, send the other packet and then send the buffered packet. Other methods may discard the contentious packets, which would result in retransmission.
The OSI model refers to what we call routers as gateways [Routers]. Routers are a lot like switches, except they deal with layer 3 of the OSI model. This is because they dont simply have to forward packets to a known address, they have to make a decision how is the packet going to get to the address? Routers have tables, but their tables contain values of LAN addresses, not actual physical addresses. This enables routers to communicate over a much larger number of nodes. Routers will typically only forward packets that are destined for networks outside of the current LAN that a node is attempting to communicate from. Routers can contain either static or dynamic tables. Static tables are created and maintained by an administrator. This can take a long time if the network is large, and the static data can become redundant if the network system is changed. Dynamic tables gather their routing information from other routers using special router protocols. There are two different strategies for communication. Distance vector involves routers sending their complete routing tables to neighboring routers. This involves a lot of overhead. Link State sends updates in their tables to their neighboring routers. This requires less overhead than distance vector, but requires a higher level of computation within the router.
When we talked about the distributed topology (in Section 1), we were inferring that routers (or IMPs) are set up in this fashion. Routers require that devices communicate using routable protocols [Routers] so that the routers understand the network activity.
When a packet is sent to a router, it will read the destination address and determine if that address is local. If it is local, it will route the packet into the subsequent LAN. If not, it will look at the network portion of the address and choose which network it needs to be sent to. The router may send the packet directly to the router on the required network, or it may need to send the packet to a router on the next hop of the journey [Routers]. There is often more than one path to a destination, so how does the router choose which it will use? The routers administrator will give it an algorithm or strategy to follow whilst routing packets.
3.3 Routing Strategies
There are many different strategies for routing packets. Each method has its advantages and disadvantages, typically characterised by cost, complexity and efficiency. Each link between routers is given a metric (or a measure of how good a certain link is) generally referred to as a cost.
3.3.1 Fixed Routing
For fixed routing, each router has a list of destination nodes and a list of next nodes. If the router cant send a packet directly to a destination, it uses the list of next nodes to work out which node to send the packet to. If the router does not know where to send a packet, it will usually have a preset destination (for example the address of the router that links the LAN with the internet). Fixed routing is an easy solution to routing for small applications, but on a larger scale it would be time-consuming to set up and dynamic costs (due to network traffic) cannot be adequately addressed using this strategy.
When using flooding as a routing strategy, each router sends the packet to all of its immediate neighbours (except to the router that sent the packet). When this strategy is used, the number of packets on the network can grow, being re-transmitted by routers. This can be overcome if routers can identify packets and make sure that packets that have been sent are not re-transmitted if they find their way back. Flooding offers a significant advantage as all paths are used, the packet will get to its destination in the shortest time possible. However, by flooding the network with packets, the network is not being used very efficiently creating a high load of network traffic.
3.3.3 Random Routing
Random routing is simple, like flooding, but occupies a lot less load on the network. Routers employing a random strategy send incoming traffic through a random outgoing link. Decisions about which route the traffic is headed is not always based on a random algorithm. In many cases a round-robin approach is taken. Since random routing doesnt use network information, it is a simple method of routing.
3.3.4 Adaptive Routing
Most packet switching networks use routers that use some form of adaptive routing. Adaptive routing means that the routing decisions made by the router change, depending on the conditions of the network around it. Routing may change if links/routers fail, or if costs of links change. Adaptive routing is complex, as it must gather and interpret information regarding costs of the network system. This means that these routers require more processing power to make routing decisions. The major benefit of adaptive routing is that it controls congestion better than any of the other major routing strategies. Since the conception of the original adaptive routing algorithm in 1969, there have been two major improvements. The newest algorithm (third generation) is more responsive to changes in the network and is generally more stable than the older versions of the adaptive routing algorithm. One problem that the third generation algorithm addresses is oscillation. Oscillation occurs when routers adapt their routing strategies simultaneously in such a fashion that routes become congested quickly. To counter this congestion, routers will again change their strategies, creating an oscillation of congestion, greatly reducing network efficiency. Oscillation is the result of "every node [was] trying to obtain the best route" [Stallings p 327], so the third generation algorithm attempts to give the average route a good path (although not necessarily the best).
3.4 Routing Methods
The actual method of transmitting data through switching equipment can be put into one of the three following categories [How LAN Switches Work]:
3.4.1 Store and Forward
Store and forward switching is one of the most popular methods of packet communication. Incoming packets are saved in a buffer and a CRC is carried out on the data to make sure the packet is error-free. The device will then look at the destination address and send the packet to the specified destination. If the packet contains an error, it will be discarded, leaving the communications protocols to re-send the lost packet. Some switching equipment will incorporate store and forward as well as cut-through methods for handling packets. Store and forward equipment usually holds the packet in its buffers until the destination has acknowledged that the packet has successfully reached its destination.
Animation 3 - Store and Forward Routing
Cut-through switching equipment reads the destination address of the packet as soon as it arrives. This address is buffered and the rest of the packet is sent to that address, eliminating the need to buffer the packet in the switching equipment. This method does not run CRCs to check for errors. For this reason, most packet switching equipment does not solely use the cut-through method. It is quite common for devices to use cut-through until a certain percentage of errors infiltrate the system, then the more reliable (but slower) store and forward method is used.
Animation 4 - Cut-Through Routing
Fragment-free is much the same as cut-through. Instead of just buffering the address, fragment-free also stores the first 64 bytes of each packet. This is because most errors and all collisions occur with the first 64 bytes of each packet. Fragment-free is not a commonly used method.