Four Component Of a Router:)
Input Port:)
- The input port's line termination function and data link processing implement the physical and data link layers associated with an individual input link to the router.
- The lookup/forwarding function of the input port is central to the switching function of the router.
- In many routers, it is here that the router determines the output port to which an arriving datagram will be forwarded via the switching fabric.
- The choice of the output port is made using the information contained in the routing table.
- a "shadow copy" of the routing table is typically stored at each input port and updated, as needed, by the routing processor.
- In routers with limited processing capabilities at the input port, the input port may simply forward the packet to the centralized routing processor, which will then perform the routing table lookup and forward the packet to the appropriate output port.
- Given the need to operate at today's high link speeds, a linear search through a large routing table is impossible. A more reasonable technique is to store the routing table entries in a tree data structure. Each level in the tree can be thought of as corresponding to a bit in the destination address.
- To lookup an address, one simply starts at the root node of the tree. If the first address bit is a zero, then the left subtree will contain the routing table entry for destination address; otherwise it will be in the right subtree.
- The appropriate subtree is then traversed using the remaining address bits -- if the next address bit is a zero the left subtree of the initial subtree is chosen; otherwise, the right subtree of the initial subtree is chosen.
- Once the output port for a packet has been determined via the lookup, the packet can be forwarded into the switching fabric.
- However, as we'll see below, a packet may be temporarily blocked from entering the switching fabric (due to the fact that packets from other input ports are currently using the fabric). A blocked packet must thus be queued at the input port and then scheduled to cross the switching fabric at a later point in time.
Switcing Fabric:)
- The switching fabric is at the very heart of a router. Switching can be accomplished in a number of ways as follows:
- Switching Via Memory: The simplest, earliest routers were often traditional computers, with switching between input and output port being done under the direct control of the CPU (routing processor). Input and output ports functioned as traditional I/O devices in a traditional operating system.
- An input port with an arriving datagram first signaled the routing processor via an interrupt.
- The packet was then copied from the input port into processor memory.
- The routing processor then extracted the destination address from the header, looked up the appropriate output port in the routing table, and copied the packet to the output port's buffers.
- Many modern routers also, switch via memory. A major difference from early routers, however, is that the lookup of the destination address and the storing (switching) of the packet into the appropriate memory location is performed by processors on the input line cards.
- Switching Via Bus:The input ports transfer a datagram directly to the output port over a shared bus, without intervention by the routing processor (Note that when switching via memory, the datagram must also cross the system bus going to/from memory).
- Only one packet at a time can be transferred over the bus at a time. A datagram arriving at an input port and finding the bus busy with the transfer of another datagram is blocked from passing through the switching fabric and queued at the input port.
- The switching bandwidth of the router is limited to the bus speed.
- Switching via a bus is often sufficient for routers that operate in access and enterprise networks
- Switching Via an Interconnection Network: Crossbar switch is an interconnection network consisting of 2N busses that connect N input ports to N output ports.
- A packet arriving at an input port travels along the horizontal bus attached to the input port until it intersects with the vertical bus leading to the desired output port.
- If the vertical bus leading to the output port is free, the packet is transferred to the output port.
- If the vertical bus is being used to transfer a packet from another input port to this same output port, the arriving packet is blocked and must be queued at the input port.
Output ports:)
- Output port processing takes the datagrams that have been stored in the output port's memory and transmit them over the outgoing link.
- The data link protocol processing and line termination are the send-side links- and physical layer functionality that interact with the input port on the other end of the outgoing link, as discussed above.
- The queuing and buffer management functionality are needed when the switch fabric delivers packets to the output port at a rate that exceeds the output link rate.
Where Does Queuing Occur?
Packet queues can form at both the input ports and the output ports. The actual location of packet loss will depend on the traffic load, the relative speed of the switching fabric, and the line speed.
Queue happens at output ports:
- Suppose that the input line speeds and output line speeds are all identical and that there are N input ports and N output ports.
- Switching fabric speed is at least N times as fast as the input line speed than no queuing can occur at the input ports.
- In the worst case, the packets arriving at each of the N input ports will be destined to the same output port. In this case, in the time it takes to receive (or send) a single packet, N packets will arrive at this output port. Since the output port can only transmit a single packet in a unit of time (the packet transmission time), the N arriving packets will have to queue (wait) for transmission over the outgoing link. N more packets can then possibly arrive in the time it takes to transmit just one of the N packets that had previously been queued. And so on. Eventually, buffers can grow large enough to exhaust the memory space at the output port, in which case packets are dropped.
- If the switch fabric is not fast enough (relative to the input line speeds) to transfer all arriving packets through the fabric without delay, then the packet queuing will also occur at the input ports.
- Head-of-the-line (HOL) blocking in an input-queued switch - a queued packet in an input queue must wait for transfer through the fabric (even though its output port is free) due to the blocking of another packet at the head-of-the-line.
