June 2010 Edition
Computer Science Department, University of Cape Town
| MSc-IT Study Material June 2010 Edition Computer Science Department, University of Cape Town |
Before discussing routers and routing, we provide some definitions.
Sub-network: a sub-network is a constituent network of an internetwork e.g. a LAN.
End-system: an end-system is a device used to support user applications, usually on a LAN, or, more specifically, part of a sub-network.
Intermediate System: A device that allows two sub-networks to communicate. Such a device is known as a router and permits communication between different network types.
Routers are devices used in both LANs and WANs. Routers (like bridges) can solve segmentation problem of LANs, although Web developers are not primarily concerned with these issues.
In a WAN, routers serve as connection points between sub-networks, more generally referred to as nodes.
Routing between sub-networks is guided by a routing table maintained in each end-system. The routing table points to the next device along a route for a packet to take in order to reach a given address. This routing table can take two forms: dynamic or static.
Static tables point to a fixed device when routing packets to a particular address. When a router fails, a message is sent out to all other tables to provide an alternative route.
Dynamic tables are regularly updated to provide alternative routes in response to heavy network traffic or router failure. Dynamic tables provide flexibility in a changing environment.
Routing tables can also support other network features, such as priority and security. A priority packet is given special privileges when passing through routers, such as shortening the delay associated with packet buffering. Packets that wish to remain at a certain security level only pass through intermediate systems with an equal or higher level of security, preventing an end-system with lower security from accessing that packet.
As the packet is passed from router to router, each router's address is appended to the packet. This record of addresses is known as a source route, and can be helpful in finding system faults.
Infinite loops and livelock are terms given to system that, through some misinterpretation, end up achieving nothing. These problems are not exclusive to internetworks.
The figure below illustrates the loop problem. In this simplified infrastructure of the Internet, orange pathways indicate a packet being passed from router device 1 to router device 2 to router device 3. The packet is then returned to router device 1, only to subsequently repeat this route through the network ad infinitum, forming an infinite loop.
This problem is overcome by giving each packet a lifetime. A packet's lifetime is a positive integer which is decremented each time the packet passes through a router. When its lifetime reaches zero, the packet is removed from the network, whether it has reached its destination or not.
More realistically, each packet can have its lifetime expressed as a time value which eventually expires. Each router must then know the time the packet last past through a router in order to properly determine the packet's remaining lifetime. This requires a global clocking mechanism that each network device follows, such as CAT (Central African Time).
Such a mechanism conveniently helps with the problem of segmentation and re-assembly.
There are many different forms of sub-network, each controlled by a protocol that specifies the maximum packet size. Unfortunately, the packet size of one form of network differs from another. Since a router provides a route of communication between networks, it also has to provide a method of transforming large packets into smaller packets. The converse of this, that is smaller to larger packets, cannot happen if the re-assembly point is the destination.
However, there are disadvantages to allowing a router to re-assemble packets:
Memory issues: reassembling packets in the router's memory can impair the performance of the router's primary function: directing packets.
Static routing: all packets must be transferred through the same router thus taking away the advantages of dynamic pathways (load balancing).
It was previously mentioned that using time to determine packet lifetime assists with data re-assembly. If the destination re-assembles packets, how long should it take to reassemble a file from separate packets?
Remember that IP does not guarantee packet delivery. This makes it necessary to have a test that determines whether or not re-assembly process should be abandoned. This is an important issue, since re-assembly takes up valuable processing time which prevents the user from using the device.
There are two approaches; the first approach uses a counter, that is measured in the local time of the end-system device. This counter is decremented during packet reassembly. When it reaches zero, the re-assembly is abandoned and a re-request is issued. The second approach uses the packet lifetime field: the lifetime continues to be decremented during re-assembly; when the lifetime expires, re-assembly is abandoned and a re-request is issued.
Do Review Question 3
While we have studied the need for protocols in computer communication, we have not examined what information is strictly necessary in order to send data between two computers on a network. This section of the unit deals with how files are sent and processed into packets, and the additional information needed to be sent with that packet so that it can reach another network machine.
The two most important additional data attached to each packet is the destination address and the order the packet is sent in (as no guarantee can be given to the order the packets will arrive in). The figure below shows the contents of an IP packet, also referred to as a datagram.
An explanation of each of these elements is provided below:
Version number: Various versions of IP exist. IPv4 is the current protocol. However, IPv6 solves some of the inadequacies (especially the low number of end-systems that IPv4 supplies) that exist in IPv4. The version number is stored in the packet, and can only be 4 bits long. Therefore there can only be 24 = 16 versions of the IP protocol.
Header length: Contains information on the length of the header and has a maximum value of 23 = 8.
Service type: Contains information concerning the reliability and delays experienced by the packet during transmission.
Total length: Is the complete length of the packet. It can have a maximum value of 216 = 65536.
Identifier: When reassembling the data packets, it is important that
each packet is associated with the same file, and
each packet is re-assembled in the order in which it was sent.
Flags: Includes six flags, one of which indicates the last packet sent.
Fragment offset: Indicates where the data contained in the packet begins.
Time to live: The measurement used to determine the lifetime of individual packets. It can be used to prevent livelock, infinite loops, and to aid the re-assembly process.
Protocol: There are many different protocols. The most common is TCP, the companion of IP, which is represented by the number 6. Other important protocols include ICMP, the Internet Control and Monitoring Protocol, represented by the number 1.
Header checksum: A small check to prevent mis-delivery of the packet.
Source address: The originating address of the packet.
Destination address: The address of the packet's destination.
Optional data: Data can include options concerning encryption, levels of security and priority of packets.
Data: The data being transmitted (i.e. the original source data).