\documentclass[11pt,twoside]{article}\makeatletter

\IfFileExists{xcolor.sty}%
  {\RequirePackage{xcolor}}%
  {\RequirePackage{color}}
\usepackage{colortbl}
\usepackage{wrapfig}
\usepackage{ifxetex}
\ifxetex
  \usepackage{fontspec}
  \usepackage{xunicode}
  \catcode`⃥=\active \def⃥{\textbackslash}
  \catcode`❴=\active \def❴{\{}
  \catcode`❵=\active \def❵{\}}
  \def\textJapanese{\fontspec{Noto Sans CJK JP}}
  \def\textChinese{\fontspec{Noto Sans CJK SC}}
  \def\textKorean{\fontspec{Noto Sans CJK KR}}
  \setmonofont{DejaVu Sans Mono}
  
\else
  \IfFileExists{utf8x.def}%
   {\usepackage[utf8x]{inputenc}
      \PrerenderUnicode{–}
    }%
   {\usepackage[utf8]{inputenc}}
  \usepackage[english]{babel}
  \usepackage[T1]{fontenc}
  \usepackage{float}
  \usepackage[]{ucs}
  \uc@dclc{8421}{default}{\textbackslash }
  \uc@dclc{10100}{default}{\{}
  \uc@dclc{10101}{default}{\}}
  \uc@dclc{8491}{default}{\AA{}}
  \uc@dclc{8239}{default}{\,}
  \uc@dclc{20154}{default}{ }
  \uc@dclc{10148}{default}{>}
  \def\textschwa{\rotatebox{-90}{e}}
  \def\textJapanese{}
  \def\textChinese{}
  \IfFileExists{tipa.sty}{\usepackage{tipa}}{}
\fi
\def\exampleFont{\ttfamily\small}
\DeclareTextSymbol{\textpi}{OML}{25}
\usepackage{relsize}
\RequirePackage{array}
\def\@testpach{\@chclass
 \ifnum \@lastchclass=6 \@ne \@chnum \@ne \else
  \ifnum \@lastchclass=7 5 \else
   \ifnum \@lastchclass=8 \tw@ \else
    \ifnum \@lastchclass=9 \thr@@
   \else \z@
   \ifnum \@lastchclass = 10 \else
   \edef\@nextchar{\expandafter\string\@nextchar}%
   \@chnum
   \if \@nextchar c\z@ \else
    \if \@nextchar l\@ne \else
     \if \@nextchar r\tw@ \else
   \z@ \@chclass
   \if\@nextchar |\@ne \else
    \if \@nextchar !6 \else
     \if \@nextchar @7 \else
      \if \@nextchar (8 \else
       \if \@nextchar )9 \else
  10
  \@chnum
  \if \@nextchar m\thr@@\else
   \if \@nextchar p4 \else
    \if \@nextchar b5 \else
   \z@ \@chclass \z@ \@preamerr \z@ \fi \fi \fi \fi
   \fi \fi  \fi  \fi  \fi  \fi  \fi \fi \fi \fi \fi \fi}
\gdef\arraybackslash{\let\\=\@arraycr}
\def\@textsubscript#1{{\m@th\ensuremath{_{\mbox{\fontsize\sf@size\z@#1}}}}}
\def\Panel#1#2#3#4{\multicolumn{#3}{){\columncolor{#2}}#4}{#1}}
\def\abbr{}
\def\corr{}
\def\expan{}
\def\gap{}
\def\orig{}
\def\reg{}
\def\ref{}
\def\sic{}
\def\persName{}\def\name{}
\def\placeName{}
\def\orgName{}
\def\textcal#1{{\fontspec{Lucida Calligraphy}#1}}
\def\textgothic#1{{\fontspec{Lucida Blackletter}#1}}
\def\textlarge#1{{\large #1}}
\def\textoverbar#1{\ensuremath{\overline{#1}}}
\def\textquoted#1{‘#1’}
\def\textsmall#1{{\small #1}}
\def\textsubscript#1{\@textsubscript{\selectfont#1}}
\def\textxi{\ensuremath{\xi}}
\def\titlem{\itshape}
\newenvironment{biblfree}{}{\ifvmode\par\fi }
\newenvironment{bibl}{}{}
\newenvironment{byline}{\vskip6pt\itshape\fontsize{16pt}{18pt}\selectfont}{\par }
\newenvironment{citbibl}{}{\ifvmode\par\fi }
\newenvironment{docAuthor}{\ifvmode\vskip4pt\fontsize{16pt}{18pt}\selectfont\fi\itshape}{\ifvmode\par\fi }
\newenvironment{docDate}{}{\ifvmode\par\fi }
\newenvironment{docImprint}{\vskip 6pt}{\ifvmode\par\fi }
\newenvironment{docTitle}{\vskip6pt\bfseries\fontsize{22pt}{25pt}\selectfont}{\par }
\newenvironment{msHead}{\vskip 6pt}{\par}
\newenvironment{msItem}{\vskip 6pt}{\par}
\newenvironment{rubric}{}{}
\newenvironment{titlePart}{}{\par }

\newcolumntype{L}[1]{){\raggedright\arraybackslash}p{#1}}
\newcolumntype{C}[1]{){\centering\arraybackslash}p{#1}}
\newcolumntype{R}[1]{){\raggedleft\arraybackslash}p{#1}}
\newcolumntype{P}[1]{){\arraybackslash}p{#1}}
\newcolumntype{B}[1]{){\arraybackslash}b{#1}}
\newcolumntype{M}[1]{){\arraybackslash}m{#1}}
\definecolor{label}{gray}{0.75}
\def\unusedattribute#1{\sout{\textcolor{label}{#1}}}
\DeclareRobustCommand*{\xref}{\hyper@normalise\xref@}
\def\xref@#1#2{\hyper@linkurl{#2}{#1}}
\begingroup
\catcode`\_=\active
\gdef_#1{\ensuremath{\sb{\mathrm{#1}}}}
\endgroup
\mathcode`\_=\string"8000
\catcode`\_=12\relax

\usepackage[a4paper,twoside,lmargin=1in,rmargin=1in,tmargin=1in,bmargin=1in,marginparwidth=0.75in]{geometry}
\usepackage{framed}

\definecolor{shadecolor}{gray}{0.95}
\usepackage{longtable}
\usepackage[normalem]{ulem}
\usepackage{fancyvrb}
\usepackage{fancyhdr}
\usepackage{graphicx}
\usepackage{marginnote}

\renewcommand{\@cite}[1]{#1}


\renewcommand*{\marginfont}{\itshape\footnotesize}

\def\Gin@extensions{.pdf,.png,.jpg,.mps,.tif}

  \pagestyle{fancy}

\usepackage[pdftitle={Up-Down Routing Based Deadlock Free Dynamic Reconfiguration in High Speed Local Area Networks},
 pdfauthor={}]{hyperref}
\hyperbaseurl{}

	 \paperwidth210mm
	 \paperheight297mm
              
\def\@pnumwidth{1.55em}
\def\@tocrmarg {2.55em}
\def\@dotsep{4.5}
\setcounter{tocdepth}{3}
\clubpenalty=8000
\emergencystretch 3em
\hbadness=4000
\hyphenpenalty=400
\pretolerance=750
\tolerance=2000
\vbadness=4000
\widowpenalty=10000

\renewcommand\section{\@startsection {section}{1}{\z@}%
     {-1.75ex \@plus -0.5ex \@minus -.2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\Large\bfseries}}
\renewcommand\subsection{\@startsection{subsection}{2}{\z@}%
     {-1.75ex\@plus -0.5ex \@minus- .2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\Large}}
\renewcommand\subsubsection{\@startsection{subsubsection}{3}{\z@}%
     {-1.5ex\@plus -0.35ex \@minus -.2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\large}}
\renewcommand\paragraph{\@startsection{paragraph}{4}{\z@}%
     {-1ex \@plus-0.35ex \@minus -0.2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\normalsize}}
\renewcommand\subparagraph{\@startsection{subparagraph}{5}{\parindent}%
     {1.5ex \@plus1ex \@minus .2ex}%
     {-1em}%
     {\reset@font\normalsize\bfseries}}


\def\l@section#1#2{\addpenalty{\@secpenalty} \addvspace{1.0em plus 1pt}
 \@tempdima 1.5em \begingroup
 \parindent \z@ \rightskip \@pnumwidth 
 \parfillskip -\@pnumwidth 
 \bfseries \leavevmode #1\hfil \hbox to\@pnumwidth{\hss #2}\par
 \endgroup}
\def\l@subsection{\@dottedtocline{2}{1.5em}{2.3em}}
\def\l@subsubsection{\@dottedtocline{3}{3.8em}{3.2em}}
\def\l@paragraph{\@dottedtocline{4}{7.0em}{4.1em}}
\def\l@subparagraph{\@dottedtocline{5}{10em}{5em}}
\@ifundefined{c@section}{\newcounter{section}}{}
\@ifundefined{c@chapter}{\newcounter{chapter}}{}
\newif\if@mainmatter 
\@mainmattertrue
\def\chaptername{Chapter}
\def\frontmatter{%
  \pagenumbering{roman}
  \def\thechapter{\@roman\c@chapter}
  \def\theHchapter{\roman{chapter}}
  \def\thesection{\@roman\c@section}
  \def\theHsection{\roman{section}}
  \def\@chapapp{}%
}
\def\mainmatter{%
  \cleardoublepage
  \def\thechapter{\@arabic\c@chapter}
  \setcounter{chapter}{0}
  \setcounter{section}{0}
  \pagenumbering{arabic}
  \setcounter{secnumdepth}{6}
  \def\@chapapp{\chaptername}%
  \def\theHchapter{\arabic{chapter}}
  \def\thesection{\@arabic\c@section}
  \def\theHsection{\arabic{section}}
}
\def\backmatter{%
  \cleardoublepage
  \setcounter{chapter}{0}
  \setcounter{section}{0}
  \setcounter{secnumdepth}{2}
  \def\@chapapp{\appendixname}%
  \def\thechapter{\@Alph\c@chapter}
  \def\theHchapter{\Alph{chapter}}
  \appendix
}
\newenvironment{bibitemlist}[1]{%
   \list{\@biblabel{\@arabic\c@enumiv}}%
       {\settowidth\labelwidth{\@biblabel{#1}}%
        \leftmargin\labelwidth
        \advance\leftmargin\labelsep
        \@openbib@code
        \usecounter{enumiv}%
        \let\p@enumiv\@empty
        \renewcommand\theenumiv{\@arabic\c@enumiv}%
	}%
  \sloppy
  \clubpenalty4000
  \@clubpenalty \clubpenalty
  \widowpenalty4000%
  \sfcode`\.\@m}%
  {\def\@noitemerr
    {\@latex@warning{Empty `bibitemlist' environment}}%
    \endlist}

\def\tableofcontents{\section*{\contentsname}\@starttoc{toc}}
\parskip0pt
\parindent1em
\def\Panel#1#2#3#4{\multicolumn{#3}{){\columncolor{#2}}#4}{#1}}
\newenvironment{reflist}{%
  \begin{raggedright}\begin{list}{}
  {%
   \setlength{\topsep}{0pt}%
   \setlength{\rightmargin}{0.25in}%
   \setlength{\itemsep}{0pt}%
   \setlength{\itemindent}{0pt}%
   \setlength{\parskip}{0pt}%
   \setlength{\parsep}{2pt}%
   \def\makelabel##1{\itshape ##1}}%
  }
  {\end{list}\end{raggedright}}
\newenvironment{sansreflist}{%
  \begin{raggedright}\begin{list}{}
  {%
   \setlength{\topsep}{0pt}%
   \setlength{\rightmargin}{0.25in}%
   \setlength{\itemindent}{0pt}%
   \setlength{\parskip}{0pt}%
   \setlength{\itemsep}{0pt}%
   \setlength{\parsep}{2pt}%
   \def\makelabel##1{\upshape ##1}}%
  }
  {\end{list}\end{raggedright}}
\newenvironment{specHead}[2]%
 {\vspace{20pt}\hrule\vspace{10pt}%
  \phantomsection\label{#1}\markright{#2}%

  \pdfbookmark[2]{#2}{#1}%
  \hspace{-0.75in}{\bfseries\fontsize{16pt}{18pt}\selectfont#2}%
  }{}
      \def\TheFullDate{2011-04-06 (revised: 06 April 2011)}
\def\TheID{\makeatother }
\def\TheDate{2011-04-06}
\title{Up-Down Routing Based Deadlock Free Dynamic Reconfiguration in High Speed Local Area Networks}
\author{}\makeatletter 
\makeatletter
\newcommand*{\cleartoleftpage}{%
  \clearpage
    \if@twoside
    \ifodd\c@page
      \hbox{}\newpage
      \if@twocolumn
        \hbox{}\newpage
      \fi
    \fi
  \fi
}
\makeatother
\makeatletter
\thispagestyle{empty}
\markright{\@title}\markboth{\@title}{\@author}
\renewcommand\small{\@setfontsize\small{9pt}{11pt}\abovedisplayskip 8.5\p@ plus3\p@ minus4\p@
\belowdisplayskip \abovedisplayskip
\abovedisplayshortskip \z@ plus2\p@
\belowdisplayshortskip 4\p@ plus2\p@ minus2\p@
\def\@listi{\leftmargin\leftmargini
               \topsep 2\p@ plus1\p@ minus1\p@
               \parsep 2\p@ plus\p@ minus\p@
               \itemsep 1pt}
}
\makeatother
\fvset{frame=single,numberblanklines=false,xleftmargin=5mm,xrightmargin=5mm}
\fancyhf{} 
\setlength{\headheight}{14pt}
\fancyhead[LE]{\bfseries\leftmark} 
\fancyhead[RO]{\bfseries\rightmark} 
\fancyfoot[RO]{}
\fancyfoot[CO]{\thepage}
\fancyfoot[LO]{\TheID}
\fancyfoot[LE]{}
\fancyfoot[CE]{\thepage}
\fancyfoot[RE]{\TheID}
\hypersetup{citebordercolor=0.75 0.75 0.75,linkbordercolor=0.75 0.75 0.75,urlbordercolor=0.75 0.75 0.75,bookmarksnumbered=true}
\fancypagestyle{plain}{\fancyhead{}\renewcommand{\headrulewidth}{0pt}}

\date{}
\usepackage{authblk}

\providecommand{\keywords}[1]
{
\footnotesize
  \textbf{\textit{Index terms---}} #1
}

\usepackage{graphicx,xcolor}
\definecolor{GJBlue}{HTML}{273B81}
\definecolor{GJLightBlue}{HTML}{0A9DD9}
\definecolor{GJMediumGrey}{HTML}{6D6E70}
\definecolor{GJLightGrey}{HTML}{929497} 

\renewenvironment{abstract}{%
   \setlength{\parindent}{0pt}\raggedright
   \textcolor{GJMediumGrey}{\rule{\textwidth}{2pt}}
   \vskip16pt
   \textcolor{GJBlue}{\large\bfseries\abstractname\space}
}{%   
   \vskip8pt
   \textcolor{GJMediumGrey}{\rule{\textwidth}{2pt}}
   \vskip16pt
}

\usepackage[absolute,overlay]{textpos}

\makeatother 
      \usepackage{lineno}
      \linenumbers
      
\begin{document}

             \author[1]{Naresh  Kumar}

             \author[2]{Renu  Vig}

             \author[3]{Deepak  Bagai}

             \affil[1]{  Kurukshetra University}

\renewcommand\Authands{ and }

\date{\small \em Received: 27 February 2011 Accepted: 22 March 2011 Published: 6 April 2011}

\maketitle


\begin{abstract}
        


Dynamic reconfiguration of high speed switched network is the process of changing from one routing function to another while the network remains in running mode. Current distributed switch-based interconnected systems require high performance, reliability and availability. These systems changes their topologies due to hot expansion of components, link or node activation and deactivation. Therefore, in order to support hard real-time and distributed multimedia applications over a high speed network we need to avoid discarding packets when the topology changes. Thus, a dynamic reconfiguration algorithm updates the routing tables of these interconnected switches according to new changed topology without stopping the traffic. Here, we propose an improved deadlock-free partial progressive reconfiguration (PPR) technique based on UP/DOWN routing algorithm that assigns the directions to various links of high-speed switched networks based on pre-order traversal of computed spanning tree. This improved technique gives better performance as compared to traditional PPR by minimizing the path length of packets to be transmitted. Moreover, the proposed reconfiguration strategy makes the optimize use of all operational links and reduces the traffic congestion in the network. The simulated results are compared with traditional PPR.

\end{abstract}


\keywords{}

\begin{textblock*}{18cm}(1cm,1cm) % {block width} (coords) 
\textcolor{GJBlue}{\LARGE Global Journals \LaTeX\ JournalKaleidoscope\texttrademark}
\end{textblock*}

\begin{textblock*}{18cm}(1.4cm,1.5cm) % {block width} (coords) 
\textcolor{GJBlue}{\footnotesize \\ Artificial Intelligence formulated this projection for compatibility purposes from the original article published at Global Journals. However, this technology is currently in beta. \emph{Therefore, kindly ignore odd layouts, missed formulae, text, tables, or figures.}}
\end{textblock*}


\let\tabcellsep& 	 	 		 \par
routing tables when there is change in network topologies due to network components failures and addition of new one. In such cases a dynamic reconfiguration algorithm analyze the new network topology and updates the routing table by replacing the old routing function with the new updated routing function. Although both routing functions are deadlockfree still it may create deadlock during reconfiguration because one of the routing function may take turns that are not allowed in the other routing function by making a cycle in the network.\par
In the literature, static reconfiguration (designed for Autonet \hyperref[b8]{[13,}\hyperref[b10]{15]} and  {\ref Myrinet[2,}\hyperref[b3]{8]} networks) replaces the routing function from old to new by stopping the network traffic. Hence it creates negative impact on the network service availability and the performance of the overall network degrades.\par
Many new schemes have been proposed recently to enhance network service availability while the network change over from one routing function to another. These new schemes updates the routing table of switched network during run time when there is any change in the network topologies due to addition/removal of links/nodes and are known as dynamic reconfiguration techniques.(Partial Progressive Reconfiguration (PPR)[3], Skyline \hyperref[b1]{[6]}, Double scheme \hyperref[b5]{[10]}, and Simple Reconfiguration \hyperref[b2]{[7]}), NetRec \hyperref[b11]{[16]} and Dynamically scaling Algorithm(DSA) \hyperref[b12]{[17]}. These schemes are designed for the networks that uses distributed routing. Double Scheme requires extra resources like virtual channels for deadlock handling that occur during transition of old routing function to new routing function. Simple reconfiguration requires a special packet called token to avoid deadlock. In this scheme firstly all packets are transmitted by old routing function, then token and finally the packet transmission is based on new routing function. NetRec was proposed as a dynamic reconfiguration scheme to increase the network availability in the presence of a permanent node fault. It restores the network connectivity by building a tree that spans all immediate neighbours of the faulty node that are still connected to network. The NetRec Scheme \hyperref[b11]{[16]} requires every switch to maintain information about nodes some number of hops away and is only applicable to wormhole networks. NetRec is 
\section[{INTRODUCTION}]{INTRODUCTION} 
\section[{H}]{H}\par
extended to dynamically reconfigure the network for the case of newly joining nodes called Dynamically Scaling Algorithm (DSA). The solution in DSA is based on performing sequence of partial routing table updates, while dropping the user messages in all selected nodes until the restoration is completed. PPR requires a sequence of synchronizing steps to progressively update old forwarding table entries to new ones while ensuring that no cycles form. The PPR [3] approach correct an invalid UP/DOWN graph after change in network topology. Double Scheme \hyperref[b5]{[10]} uses the concept of virtual channels to avoid deadlock while reconfiguring the network . Simple Reconfiguration \hyperref[b2]{[7]} uses a packet called a token to avoid deadlock by ensuring that the packet which belongs to old routing function are transmitted first, then the token, and finally packet transmission is based on the new routing function. A management mechanism \hyperref[b6]{[11,}\hyperref[b7]{12]} and zeroconfiguration hierarchical UP/DOWN routing[19] has been discussed for distributed calculation of the new routing function when there is any change in the switched-network topology. In this mechanism the distributed path-computation gives better performance when compared to existing centralized pathcomputation, still the routing function was updated statically, therefore degrades the performance.\par
In this research work, we propose to apply a new and very efficient dynamic reconfiguration strategy based on PPR that makes transformation of an invalid UP/DOWN graph (that is due to change in topology) into a valid UP/DOWN graph, while ensuring that there is no cycles in the graph to make it deadlock-free. Moreover, our dynamic reconfiguration does not use any additional resources such as virtual channels or special packet a token. This new proposed scheme gives better performance than PPR by distributing the traffic through optimize use of all links and reducing the congestion on root node of the spanning tree.\par
The next section discuss the concepts of UP/DOWN routing based PPR scheme and provides background information on previous studies of reconfiguration of UP/DOWN routing networks. Section 3 gives the details of improved dynamic reconfiguration strategy and assigning the directions UP/DOWN to the operational links based on pre-order traversal of spanning tree. In section 4, the performance of the proposed reconfiguration strategy is evaluated. Finally, section 5 concludes this research work and proposes some future work.\par
PPR scheme is based on deadlock-free UP/DOWN routing algorithm \hyperref[b9]{[14]} for irregular network topologies . The UP/DOWN routing algorithm is based on a cycle-free assignment of directions to the operational links in the network. For each link in the network, one direction is named up and the other is down. Deadlock avoidance is achieved by using legal routes. A packet never use a link in the up direction after having used one in the down direction. Messages can traverse zero or more links in the up direction, followed by zero or more links in the down direction. Therefore, deadlocks are prevented and cycles in the channel dependency graph \hyperref[b0]{[4]} are avoided. Major problem of old PPR is the random assignment of UP/DOWN direction to links between two or more nodes at the same label.\par
A sink node [3] does not have outgoing uplinks( a node that is not the source of any link). There are no legal routes between any two sink nodes due to the restrictions imposed by UP/DOWN routing algorithm because each route would require a down to up transition, which is not allowed. So there is always a single sink node in directed acyclic graph based on UP/DOWN routing algorithm. A break node is the source of two or more links. This node breaks the cycles formation to avoid deadlock in directed graph. The graph of Fig 1 includes various break nodes like node j, e, d. A correct graph contains a single sink node for UP/DOWN routing. It includes as many break nodes as necessary to break all cycles for deadlock freedom. The graph shown in Fig 1 is a correct graph. On the other hand, an incorrect graph does not meet the restrictions imposed in the correct graph. An incorrect graph has the absence of a sink node, presence of more than one sink node, or there are cycles in the graph. Fig. \hyperref[fig_1]{2} tells about an incorrect graph with two sink nodes ?b' and ?c' after removal of node ?a' from Fig.  {\ref 1} correct graph. A PPR scheme changes the direction of operational links to give a correct graph from an incorrect graph as shown in Fig.  {\ref 3}.In the literature, several algorithms have been proposed for constructing an UP/Down directed graph. Traditional proposals are based on the computation of a spanning tree which is built using a breadth-first search (BFS) \hyperref[b9]{[14]}, a depth-first search(DFS) \hyperref[b8]{[13]}, or a propagation-order spanning tree(POST) \hyperref[b10]{[15]}. 
\section[{Network}]{Network}\par
topology changes due to addition/removal of switches/ links, then our dynamic reconfiguration scheme calculates a new routing function which ensures that packets that belong to the new routing function can not take turns in the old routing function, and vice versa. Therefore, packets of old and new routing functions can unrestrictedly coexist in the network without creating deadlocks. This improved PPR scheme is based on the concept of assigning the UP/DOWN directions to operational links by pre-order traversal of spanning tree in which a unique label is for each node of the graph. We also present lemmas to support that, when an UP/DOWN graph for the new topology is designed based on pre-order traversal of spanning tree, the routing function is updated without the risk of transient deadlocks. 
\section[{Definition 1}]{Definition 1}\par
Assume that two UP/DOWN directed graphs, G1 and G2, represented two network topologies. Then G1 and G2 are corrected.\par
Fig 4 presents UP/DOWN graph G1 which is correct. Fig. 5 shows again a correct graph G2 after removal of root node ?a' of graph G1 in Fig. 4 Lemma1\par
Assume that an UP/DOWN directed graph G1 based on pre-order traversal of spanning tree is correct. Then, it is always possible to obtain a correct graph G2 from G1 when any node or link is added or removed. 
\section[{Proof}]{Proof}\par
In a correct UP/Down graph, each possible cycle must contain at least one node with two incoming up-links and at least one node with two outgoing uplinks.         a b c d e f g h i j k a [x] [0] [1] [0,1] [0,1] [0] [1] [1] [1] [0,1] [1] b [0] [x] [0] [1] [2,0] [3] [0] [0] [0] [1,2,3,0] [0] c [0] [0] [x] [1,0] [2,0] [0] [3] [4] [5] [1,2, 3,4,0] [3,5] d [0,1] [0,1] [1,0] [x] [0,1] [0] [1,0] [1,0] [1,0] [2,1,0] [1,0] e [0,2] [0,2] [2,0] [0,2] [x] [0] [2,0] [2,0] [2,0] [1,2,0] [2,0] f [0] [0] [0] [0] [0] [x] [0] [0] [0] [1,0] [0] g [0] [0] [0] [0] [0] [0] [x] [0] [1,0] [2,0] [0] h [0] [0] [0] [0] [0] [0] [0] [x] [0] [1,0] [0] i [0] [0] [0] [0] [0] [0] [0] [0] [x] [0] [1 ,0] j [0,1,2, 3,4] [0,1,2, 3,4] [1,3,4 ,2,0] [0,1, 2,3,4] [1,2,0 ,3,4] [2,1, 0,3,4] [3,4, 2,1,0] [4,3,2, 1,0] [4,3,2 ,1,0] [x] [4,3,2 ,1,0] k [0,1] [0,1] [0,1] [0,1] [0,1] [0,1] [0,1] [0,1] [1,0] [0,1] [x]b c d e f g h i j k b [x] [2] [1] [2] [3] [1,2] [1,2] [1,2] [1,2,3] [1,2] c [1,2] [x] [1,2] [2,1] [1,2] [3] [4] [5] [3,4, 1,2] [3,5] d [0] [1,0] [x] [0] [0] [1,0] [1,0] [1,0] [2,1,0] [1,0] e [0] [2,0] [0] [x] [0] [2,0] [2,0] [2,0] [1,2,0] [2,0] f [0] [0] [0] [0] [x] [0] [0] [0] [1,0] [0] g [0] [0] [0] [0] [0] [x] [0] [0] [1,0] [2,0] h [0] [0] [0] [0] [0] [0] [x] [0] [1,0] [0] i [0] [0] [0] [0] [0] [0] [0] [x] [0] [1,0] j [0,1,2 ,3,4] [0,1, 3,4,2] [0.1.2 .3.4] [1,0,2 ,3,4] [2,0, 1,3,4] [3,0, 1,2,4] [4,0, 1,2,3] [3,4 ,0,1,2] [x] [3,0, 1,2,4] k [0,1] [0,1] [0,1] [0,1] [0,1] [0,1] [0,1] [1,0] [1,0] [x]j k a [x] [0] [1,0] [0] [0] [0] [1,0] [1,0] [1,0] [0] [1,0] b [0] [x] [0,2,1] [1] [2,1] [3,1] [0,1] [0,1] [0,1] [1] [0,1] c [0,1,2] [0,1] [x] [1,0,2] [2,0,1] [0,1,2] [3,2, 1,0] [4,2, 1,0] [5,3, 2,1,0] [2,1,0] [3,2, 1,0] d [0] [0] [1,0,2] [x] [0,2] [0,2] [1,2,0] [1,2,0] [1,0,2] [2] [1,2,0] e [0,1] [0,1] [2,0] [0,1] [x] [0,1] [1,2,0] [1,2,0] [2,0,1] [1,0] [1,2,0] f [0,1] [0,1] [0,1] [0,1] [0,1] [x] [1,0] [1,0] [1,0] [1,0] [1,0] g [0,1] [0,1] [0,1] [1,0] [1,0] [1,0] [x] [0,1] [0,1,2] [1,0] [2] h [0,1] [0,1] [0,1] [1,0] [1,0] [1,0] [1,0] [x] [0,1] [1,0] [1] i [0,1] [0,1] [0,1] [0,1] [0,1] [0,1] [0,1] [0,1] [x] [0,1] [1,0] j [0] [0] [0] [0] [1,0] [2,0] [3,0] [4,0] [3,1,0] [x] [3,1,0] k [0] [0] [0] [0] [0] [0] [0] [0] [1,0] [0] [x]i Switch b c d e f g h i j k b [x] [1,2] [1] [2,1] [3,1] [1,2] [1,2] [1,2] [1] [1,2] c [1,2] [x] [1,2] [2,1] [2,1] [3,2,1] [4,2,1] [5,2,1] [1,2] [3,2,1] d [0] [1,2,0] [x] [0,2] [0,2] [2,1,0] [2,1,0] [1,0,2] [2] [1,2,0] e [0,1] [2,1,0] [0,1] [x] [0,1] [2,1,0] [2,1,0] [2,1,0] [1,0] [2,1,0] f [0,1] [0,1] [0,1] [0,1] [x] [1,0] [1,0] [1,0] [1,0] [1,0] g [0,1] [0,1] [0,1] [0,1] [1,0] [x] [0,1] [0,2,1] [1,0] [2,1,0] h [0,1] [0,1] [0,1] [0,1] [1,0] [0,1] [x] [0,1] [1,0] [0,1] i [0,1] [0,1] [0,1] [0,1] [0,1] [0,1] [0,1] [x] [1,0] [1,0] j [0] [1,0] [0] [1,0] [2,0] [3,0] [4,0] [3,1,0] [x] [3,1,0] k [0] [0] [0] [0] [0] [0] [0] [1,0] [0] [x]j k l m b [X] [1,2] [1] [2,1] [3,1] [1,2] [1,2] [1,2] [1] [1,2] [1] [1,2] c [1,2] [X] [5] [3,1,0] k [0] [0] [0] [0] [0] [0] [0] [1,0] [0] [X] [0] [2] l [0] [0] [0] [0] [0] [0] [0] [0] [0] [0] [X] [0] m [0] [0] [0] [0] [0] [0] [0] [0] [0] [0] [0] [X]\par
cycle in G2, we have three options with respect to break node placement. Thus, it is always possible to construct a correct graph G2 which is also like G1. A correct graph G1 in Assume that two up/down directed graphs G1 and G2 where G2 is also correct after removal of any node or link of correct graph G1 Proof Assume that G2 is a subgraph of G1 in which each link that connects a break node in G1 with the corresponding break node in G2 is suppressed, and that G2 is a correct UP/DOWN graph. Then, according to lemma 1, we can guarantee that G2 is also a correct UP/DOWN graph. Thus it possible to define a fully connected deadlock-free routing function R2 over G2. R2 satisfies the routing-restrictions of both G1 and G2 since all the break nodes either have the same locations or have been removed.\par
Preorder Traversal Based UP/DOWN direction assignment to various link. 1) Computing a spanning tree.\par
2) Preorder traversal of spanning tree and assign labeling to nodes through horizontal traversal based distance of each node from root node. 3) Next assigning UP/DOWN directions to various links likewise previous strategy. 4) Finally, updation of routing tables 
\section[{Switch Deactivation}]{Switch Deactivation}\par
The deactivation of switch including the root node produces a new root node. Switch deactivations imply that messages routed to remove components must be discarded. In this case, shorter reconfiguration time implies less discarded messages which is the characteristic of this improved PPR scheme. 
\section[{Switch Activation}]{Switch Activation}\par
When a new switch is added, a direction must be assigned to the links connecting to it in such a way that the down direction goes toward the new switch and it should no produce cycles in the directed graph.\par
In this section, we evaluate the performance of the improved PPR algorithm proposed in section 3. Our dynamic reconfiguration scheme is compared to traditional PPR scheme. New mechanism requires very less computations time for updation of routing function from old one to new, when there is change in network topology due to addition or removal of switch nodes or links. 
\section[{a) Switch Model}]{a) Switch Model}\par
A switch consist of crossbar, a routing and configuration unit, and many full-duplex links. The routing and configuration unit provides the output channel for multiple packets to cross a switch. Table look-up routing is used. Each input channel has 2 set of buffers: user and control buffers. Control buffers handle control messages generated in each reconfiguration process when there is any change in network topology.\par
We have assumed that one clock cycle is required to access the routing table and provide the output link for the message. The high-speed switched networks are consist of a set of switches interconnected through point-topoint links and hosts are connected to those switches through a network interface card in a irregular fashion. We have evaluated the performance of different sizes of networks. Several different networks with irregular topologies are considered in order to perform a detailed study. The irregular topologies have been randomly generated. 
\section[{c) Message Generation}]{c) Message Generation}\par
For each simulation run, we have considered that message generation rate is constant and the same for all the nodes. Once the network has reached a steady state, the flit generation rate is equal to the flit reception rate(traffic).We have evaluated the full range of traffic, from low load to saturation. On the other hand, we have considered the message destination is randomly chosen among all the nodes d) Simulation Results\par
In this section, we show the simulation results for improved PPR scheme based on pre-order traversal of spanning tree. The simulation results are compared with existing PPR scheme. The simulation used for this work is developed with the IRFlexiSim Simulator \hyperref[b13]{[18]}. First of all, we have discussed the way in which the path computation time is reduced by using improved PPR strategy in section 3. In order to increase the accuracy of the results, each experiment is repeated several times. The numbers of simulation runs for each topology are presented graphically. The number of data packets that are discarded during the topology change assimilation process gives an indication of the level of service a network can provide to applications. Fig.  {\ref 8} compares the amount of packets that are discarded for PPR and improved PPR scheme. The results in Fig  {\ref 8} shows that, for a switch removal the rate at which data packets are discarded is notably lower for new PPR scheme. The main reason is that, for improved PPR scheme minimum changes are required to update the routing tables. In case of switch additions, no packets are discarded due to inactive ports because no old roots include the switch that was just added. There is no packet discarding when a switch addition occur because it does not destroy any of the existing paths. To conclude this evaluation, Figures as shown below illustrates the instantaneous behavior of both the old PPR and new PPR scheme. The improved PPR scheme reduces the number of packets discarded during reconfiguration and increases the performance by distributing the traffic over all links of the network. Thus, it reduces the latency of packets and increases throughput by optimize use of all links and lowering the congestion at root node as shown in Fig  {\ref 9}. Use In this paper, we have proposed and evaluated a simple improved reconfiguration strategy to compute the UP/DOWN routing tables. The improved methodology makes use of pre-order traversal of spanning tree in order to assign UP and DOWN directions to links is able to impose less routing restrictions to remove the cyclic channel dependencies in the network than those imposed when using the paths and a better traffic balance, thus increasing channel utilization in the network .At a minor computational cost, the new routing function is designed to ensure that packets routed according to the old and the new routing functions can unrestrictedly coexist in the network, without the risk of forming deadlocks. Simulation results show that this significantly reduces the amount of packets that are discarded during the topology change assimilation. Moreover, our strategy does not required additional resources such as virtual channels, and it could easily be implemented in current commercial systems. As future work, we plan to extend the proposed methods in order to support other routing algorithms in addition to UP/DOWN. \begin{figure}[htbp]
\noindent\textbf{}\includegraphics[]{image-2.png}
\caption{\label{fig_0}Fig1:}\end{figure}
 \begin{figure}[htbp]
\noindent\textbf{2}\includegraphics[]{image-3.png}
\caption{\label{fig_1}Fig. 2}\end{figure}
       \begin{figure}[htbp]
\noindent\textbf{1} \par 
\begin{longtable}{P{0.85\textwidth}}
Switch\end{longtable} \par
 
\caption{\label{tab_0}Table 1 :}\end{figure}
 \begin{figure}[htbp]
\noindent\textbf{3} \par 
\begin{longtable}{P{0.425\textwidth}P{0.053125\textwidth}P{0.053125\textwidth}P{0.053125\textwidth}P{0.053125\textwidth}P{0.053125\textwidth}P{0.053125\textwidth}P{0.053125\textwidth}P{0.053125\textwidth}}
Switch a\tabcellsep b\tabcellsep c\tabcellsep d\tabcellsep e\tabcellsep f\tabcellsep g\tabcellsep h\tabcellsep i\end{longtable} \par
 
\caption{\label{tab_1}Table 3}\end{figure}
 \begin{figure}[htbp]
\noindent\textbf{4} \par 
\begin{longtable}{}
\end{longtable} \par
 
\caption{\label{tab_2}Table 4 :}\end{figure}
 \begin{figure}[htbp]
\noindent\textbf{5} \par 
\begin{longtable}{P{0.425\textwidth}P{0.06071428571428571\textwidth}P{0.06071428571428571\textwidth}P{0.06071428571428571\textwidth}P{0.06071428571428571\textwidth}P{0.06071428571428571\textwidth}P{0.06071428571428571\textwidth}P{0.06071428571428571\textwidth}}
Switch\tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \\
b\tabcellsep c\tabcellsep d\tabcellsep e\tabcellsep f\tabcellsep g\tabcellsep h\tabcellsep i\end{longtable} \par
 
\caption{\label{tab_3}Table 5}\end{figure}
 \begin{figure}[htbp]
\noindent\textbf{} \par 
\begin{longtable}{P{0.6917132216014897\textwidth}P{0.025325884543761636\textwidth}P{0.1329608938547486\textwidth}}
\tabcellsep \tabcellsep 2011\\
\tabcellsep \tabcellsep 69\\
\multicolumn{2}{l}{1. Advanced Switching Interconnect Special Interest Group, Advanced Switching Core Architecture Specification Revision 1.0 ,Discarded Packets 2 4 N 2 4 L 1 6 N 1 6 L 1 2 N 1 2 L 0 20 40 60 80 100 120 140 160 180 8 N 3 2 L 3 2 N 4 8 L 4 8 N 6 4 L 6 4 N 1 0 0 L PPR Improved PPR}\tabcellsep Volume XI Issue VII Version I\\
Network Size(Switches)\tabcellsep \tabcellsep \\
Path Lenth 2 4 N 3 2 L 1 6 N 2 4 L 1 2 N 1 6 L 8 N 1 2 L 0 1 2 3 4 5 6 7 8 9 3 2 N 4 8 L 4 8 N 6 4 L 6 4 N 1 0 0 L NeI twork Size(Switches)\tabcellsep Improved PPR PPR\tabcellsep Global Journal of Computer Science and Technology\end{longtable} \par
 
\caption{\label{tab_4}}\end{figure}
 			\footnote{May Up-Down Routing Based Deadlock Free Dynamic Reconfiguration in High Speed Local Area Networks ©2011 Global Journals Inc. (US)} 			\footnote{May Up-Down Routing Based Deadlock Free Dynamic Reconfiguration in High Speed Local Area Networks ©2011 Global Journals Inc. (US)} 			\footnote{May Up-Down Routing Based Deadlock Free Dynamic Reconfiguration in High Speed Local Area Networks ©2011 Global Journals Inc. (US)} 			\footnote{May Up-Down Routing Based Deadlock Free Dynamic Reconfiguration in High Speed Local Area Networks ©2011 Global Journals Inc. (US)} 			\footnote{May Up-Down Routing Based Deadlock Free Dynamic Reconfiguration in High Speed Local Area Networks ©2011 Global Journals Inc. (US) Lemma 2} 		 		\backmatter  			  				\begin{bibitemlist}{1}
\bibitem[Lbanez et al. ()]{b13}\label{b13} 	 		\textit{},  		 			Guillermo Lbanez 		,  		 			Alberto Garcia -Martinez 		,  		 			Juan A Carral 		,  		 			Pedro A Gonzalez 		,  		 			Arturo Azcorra 		,  		 			Jose M Arco 		.  		 HURP/HURBA: Zero-configuration.  		 \url{http://www.ceng.usc.edu/smart/tools.html19}  		2010.  	 
\bibitem[Avresky et al. (2004)]{b12}\label{b12} 	 		‘?Dynamically Scaling System Area Networks?’.  		 			D R Avresky 		,  		 			Y Varoglu 		,  		 			M Marinov 		.  	 	 		\textit{IEEE Proceedings of the 12 th EuroMicro Conference On Parallel , Distributed and Network-Based Processing},  				Feb 2004. p. .  	 
\bibitem[Robles -Gómez et al. ()]{b6}\label{b6} 	 		‘A Model for the Development of ASI Fabric Management References Références Referencias Protocols’.  		 			A Robles -Gómez 		,  		 			E M García 		,  		 			A Bermúdez 		,  		 			R Casado 		,  		 			F J Quiles 		.  	 	 		\textit{LNCS}  		Nagel, W.E., Walter, W.V., Lehner, W. (ed.)  		2006. 2006. Springer. 4128.  	 
\bibitem[Sancho et al. (2000)]{b9}\label{b9} 	 		‘A new methodology to compute deadlock-free routing tables for irregular networks’.  		 			J C Sancho 		,  		 			A Robles 		,  		 			J Duato 		.  	 	 		\textit{Proc. the 4th Workshop on Communication, Architecture, and Applications for Network-based Parallel Computing},  				 (the 4th Workshop on Communication, Architecture, and Applications for Network-based Parallel Computing)  		January 2000.  	 
\bibitem[Robles-Gómez et al. ()]{b7}\label{b7} 	 		‘A proposal for managing ASI fabrics’.  		 			A Robles-Gómez 		,  		 			A Bermúdez 		,  		 			R Casado 		,  		 			F J Quiles 		,  		 			T Skeie 		,  		 			J Duato 		.  	 	 		\textit{Journal of System Architecture (JSA)}  		2008.  	 
\bibitem[Rodeheffer and Schroeder (1991)]{b8}\label{b8} 	 		‘Automatic reconfiguration in Autonet’.  		 			T L Rodeheffer 		,  		 			M D Schroeder 		.  	 	 		\textit{SRC Research Report 77 of the ACM Symposium on Operating Systems Principles},  				October 1991.  	 
\bibitem[Schroeder et al. (1991)]{b10}\label{b10} 	 		‘Autonet: a high-speed, self-configuring local area network using point-to-point links’.  		 			M D Schroeder 		,  		 			A D Birrell 		,  		 			M Burrows 		,  		 			H Murray 		,  		 			R M Needham 		,  		 			T L Rodeheffer 		,  		 			E H Satterthwate 		,  		 			C P Thacker 		.  	 	 		\textit{IEEE Journal on Selected Areas in Communications}  		October 1991. 9  (8) .  	 
\bibitem[Dally and Seitz ()]{b0}\label{b0} 	 		‘Deadlock-free message routing in multiprocessor interconnection networks’.  		 			W J Dally 		,  		 			C L Seitz 		.  	 	 		\textit{IEEE Transactions on Computers}  		1987. 36  (5) .  	 
\bibitem[Pinkston et al. (2003)]{b5}\label{b5} 	 		‘Deadlockfree dynamic reconfiguration schemes for increased network dependability’.  		 			T M Pinkston 		,  		 			R Pang 		,  		 			J Duato 		.  	 	 		\textit{IEEE Transactions on Parallel and Distributed Systems}  		June 2003. 14  (6) .  	 
\bibitem[Netrec and Avresky ()]{b11}\label{b11} 	 		\textit{Dependable Network Computing},  		 			; Netrec 		,  		 			Dimiter Avresky 		.  		2000. Dordrecht: Kluwer Academic Publishers. p. 10.  	 
\bibitem[Lysne and Duato (2000)]{b1}\label{b1} 	 		‘Fast dynamic reconfiguration in Irregular networks’.  		 			O Lysne 		,  		 			J Duato 		.  	 	 		\textit{Proc. Int.Conference on Parallel Processing},  				 (Int.Conference on Parallel essing)  		August 2000.  	 
\bibitem[Myrinet ()]{b3}\label{b3} 	 		 			Inc Myrinet 		.  		 \url{http://www.myri.com/}  		\textit{Guide to Myrinet-, Switches and Switch Networks},  				2000.  	 
\bibitem[Lysne et al. (2004)]{b2}\label{b2} 	 		‘Simple deadlockfree dynamic network reconfiguration’.  		 			O Lysne 		,  		 			J M Montañana 		,  		 			T M Pinkston 		,  		 			J Duato 		,  		 			T Skeie 		,  		 			J Flich 		.  	 	 		\textit{Proc. of the International Conference on High Performance Computing},  				 (of the International Conference on High Performance Computing)  		December 2004.  	 
\bibitem[Horst (1995)]{b4}\label{b4} 	 		‘Tnet: A reliable System area network’.  		 			R Horst 		.  	 	 		\textit{IEEE Micro}  		Feb. 1995. p. .  	 
\end{bibitemlist}
 			 		 	 
\end{document}
